HDU 1576:A/B

要求(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
 
分析,我们要求的是(A/B)%9973,这个试子可以等价为( (a%9973)*_b )\%9973,其中_b为B的逆元。可以看到a%9973正好就是题中所给的n。
所以题目就是求出B的逆元而已。

代码:

#include <iostream>

using namespace std;
void Ex_gcd(int a, int b, int &x, int &y)
{
    if(b == 0)//递归出口
    {
        x = 1;
        y = 0;
        return;
    }
    int x1, y1;
    Ex_gcd(b, a%b, x1, y1);
    x = y1;
    y = x1-(a/b)*y1;
}
int MOD(int &n,int &f)
{
   return (n%9973)*(f%9973)%9973;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,B;
        cin>>n>>B;
        int x,y;
        Ex_gcd(B,9973,x,y);
        if (x<0)
            x+=9973;
        int f=x;
        int result=MOD(n,f);
        cout<<result<<endl;
    }
    return 0;
}
0

Leave a Reply

Your email address will not be published.