原题传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1576
A/B
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1929 Accepted Submission(s): 1421
Problem Description
要求(A/B)%9973,但由于A很大,我们只给出n(n=A%9973)(我们给定的A必能被B整除,且gcd(B,9973) = 1)。
Input
数据的第一行是一个T,表示有T组数据。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
Output
对应每组数据输出(A/B)%9973。
Sample Input
2
1000 53
87 123456789
Sample Output
7922
6060
Author
xhd
Source
Recommend
/** 方法一: A = n+9973k; (k为大于等于0的正整数) 令x = A/B;则A = B*x; => B*x = n+9973k; => B*x - 9973k = n; 再由方程B*x1 + 9973y1 = gcd(B,9973); 如果能解出x1,那么x = nx1; k取-ny1的时候, 方程B*x - 9973k = n 成立; 现在的问题是怎么解出x1? 当然是扩展欧几里德算法啊! 题目中gcd(B,9973) = 1; 对于方程Bx1 + 9973y1 = 1; */ #include<cstdio> #define MOD 9973 int n,B; int t,x,y,d; void ex_gcd(int a,int b,int &d,int &x,int &y) { if(b==0){d = a;x=1;y=0;} else{ ex_gcd(b,a%b,d,y,x); y = y-(a/b)*x; } } int main() { scanf("%d",&t); while(t--) { d = 1; scanf("%d%d",&n,&B); ex_gcd(B,MOD,d,x,y); x = n*x; printf("%d\n",(x%MOD+9973)%MOD); } return 0; } /** 方法二: A = n+9973k; (k为大于等于0的正整数) 令C = A/B; C = t*9973 + x;这里x为所求(A/B)%9973; 则A = B*C = B*t*9973 + B*x ; =>n+9973k = 9973Bt +Bx; =>9973k = 9973Bt + (Bx - n); 所以(Bx - n)%9973 = 0; 应为x<9973;枚举就可以解决 */ #include<cstdio> #define MOD 9973 long long n,B; int t,x; int main() { scanf("%d",&t); while(t--) { x = 0; scanf("%I64d%I64d",&n,&B); while((B*x-n)%9973 != 0) { x++; } printf("%d\n",x); } return 0; }
相关推荐
现在,给你两个正的小数A和B,你的任务是代表大明计算出A+B的值。 Input 本题目包含多组测试数据,请处理到文件结束。 每一组测试数据在一行里面包含两个长度不大于400的正小数A和B。 Output 请在一行里面...
acm hdu as easy as a+b
8 5513979-A WP471-A×1 & SH281-B×2 (DKA) 2 SP 9 5513979-B WP471-B×1 & SH281-B×4 (DKA) 2 SP 10 5513976-A WP490-A P/K ASSY (CACHE) 2 SP 11 5513975-C WP481-C P/K ASSY (CSW-S) 2 SP 12 5513977-B SH288-B...
本资源为HDU数字图像处理课程 浙江省在线平台的视频课后作业 仅供参考 假设我们有一个mat型的单通道图像,命名为srcMat,我们想得到第i行,第j列的像素值则可以用一下的代码 A. int value= srcMat.at<Vec3b>(i)(j)[0...
杭电OJ部分答案,可以很简单的解决a+b求和问题及其他问题。
very very good friends -________-b FF is a bad boy, he is always wooing TT to play the following game with him. This is a very humdrum game. To begin with, TT should write down a sequence of integers...
投入产出练习的A + B(I) 投入产出练习的A + B(II) 投入产出练习的A + B(III) 投入产出练习的A + B(IV) 输入输出练习的A + B(V) 投入产出练习的A + B(VI) 投入产出练习的A + B(VII) 投入产出...
hdu6425 Rikka with Badminton(2018 Multi-University Training Contest 9)共n个人,每个人可...a个人没球没拍,b个人有拍,c个人有球,d个人有球有拍。有俩拍一球即可举办比赛。问不能举办比赛的可能情况有多少?
(a)输入图像,(b)cGAN,(c)CA-GAN,(d)SCA-GAN 先决条件 Linux或类似环境 Python 2.7 NVIDIA GPU + CUDA CuDNN 入门 安装 克隆此仓库: git clone https://github.com/fei-hdu/ca-gan cd ca-gan 从安装...
B 的约数之和对 MOD 取模 . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.13 莫比乌斯反演 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.13.1 莫比乌斯函数 . . . ...
实现四个USB-A 母座 下行端口和一个USB-B 母座 上行端口以最高近似 5Gbps(SuperSpeed)的速率传输数据; 设备可以通过 5.5 外径 2.5 内径 DC 电源接口供电,供电电压为 9V~14V DC,所需适配器功率不低于 45W *; 在...
实现四个USB-A 母座 下行端口和一个USB-B 母座 上行端口以最高近似 5Gbps(SuperSpeed)的速率传输数据; 设备可以通过 5.5 外径 2.5 内径 DC 电源接口供电,供电电压为 9V~14V DC,所需适配器功率不低于 45W *; 在...
MF000011 : hdua45 MF000012 : hud6hj MF000013 : husn56 MF000014 : dehi34 MF000015 : hsung5 MF000016 : 45fjis MF000017 : huugn9 MF000018 : khnf54 MF000019 : hudn56 MF000020 : khfunw MF000021 : djdhnd MF...