hdu 1576 A/B 拓展欧几里得算法

A/B

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2390    Accepted Submission(s): 1731

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)。
 
Output
对应每组数据输出(A/B)%9973。
 
Sample Input
2
1000 53
87 123456789
 
Sample Output
7922
6060
 
Author
xhd
 
  对于拓欧我用的一点也不熟练,特别是限制解必须为正数时,而本题规定了b,9973互质,直接取模至正数,还变简单了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long qword;
qword ext_gcd(qword a,qword b,qword &x,qword &y)
{
if (a%b==)
{
//a*x+b*y==b
x=;y=;
return y;
}
qword ret=ext_gcd(b,a%b,x,y);
qword tx=x,ty=y;
x=ty;
y=tx-a/b*ty;
return ret;
}
int main()
{
//freopen("input.txt","r",stdin);
//A=9973*x+n
//(9973*x+n)=y*B
//9973*x-B*y==-n
qword n,a,b,x,y,yy,xx;
int nn;
scanf("%d",&nn);
qword g;
while (nn--)
{
scanf("%I64d%I64d",&n,&b);
g=ext_gcd(,b,x,y);
x*=-n;y*=n;
// cout<<9973*x-b*y<<endl;
yy=(y%+)%;
xx=x-(y-yy)/*b;
// cout<<9973*xx-b*yy<<endl;
cout<<yy<<endl;
}
}
上一篇:php字符串格式化函数addslashes()


下一篇:使用CoreRT将.NET Core发布为Native应用程序