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

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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了hdu 1576 A/B 拓展欧几里得算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1259字，纯文字阅读大概需要2分钟。

内容图文

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>
usingnamespace std;
typedef longlong 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;
        }
}

 

原文：http://www.cnblogs.com/mhy12345/p/4057678.html

内容总结

以上是互联网集市为您收集整理的hdu 1576 A/B 拓展欧几里得算法全部内容，希望文章能够帮你解决hdu 1576 A/B 拓展欧几里得算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1060331.html

来源：【匿名】