现在的位置: 首页 > 综合 > 正文

HDU 1576 A/B 扩展欧几里得

2014年09月03日 ⁄ 综合 ⁄ 共 880字 ⁄ 字号小中大 ⁄ 评论关闭

A/B

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

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

Source

HDU 2007-1 Programming Contest

Recommend

linle

因为n=A%9973，所以可以的得到A=9973*y+n，又因为A/B=x，所以A=B*x。因此可得方程B*x-9973*y=n，最后用欧几里得算法解出来就可以了。

#include<stdio.h>
int exgcd(int A,int &x,int B,int &y)
{
    int x1,y1,x0,y0;
    x0=1;y0=0;
    x1=0;y1=1;
    int r=(A%B+B)%B;
    int q=(A-r)/B;
    x=0;y=1;
    while(r)
    {
        x=x0-q*x1;
        y=y0-q*y1;
        x0=x1;
        y0=y1;
        x1=x;y1=y;
        A=B;B=r;r=A%B;
        q=(A-r)/B;
    }
    return B;
}
int main()
{
    int t,n,b,x,y;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&b);
        int ans=exgcd(b,x,9973,y);
        int k=9973/ans;
        x*=(n/ans);
        x=(x%k+k)%k;
        printf("%d\n",x%9973);
    }
    return 0;
}