首页 > 代码库 > hdu 1576 A/B 拓展欧几里得算法
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)。
每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。
Output
对应每组数据输出(A/B)%9973。
Sample Input
21000 5387 123456789
Sample Output
79226060
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==0) { //a*x+b*y==b x=0;y=1; 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(9973,b,x,y); x*=-n;y*=n; // cout<<9973*x-b*y<<endl; yy=(y%9973+9973)%9973; xx=x-(y-yy)/9973*b; // cout<<9973*xx-b*yy<<endl; cout<<yy<<endl; }}
hdu 1576 A/B 拓展欧几里得算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。