A/B(逆元)

A/B

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

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

 

 

 

就是问你会不会求模的逆元，A/B 的模不能直接除了就取余，要当做 (A* (1/B) ）%m 所以就是求 1/B(即B关于MOD的乘法逆元)

费马小定理:  当m为质数的时候  A^{^(m-1)} = 1   (mod m) 即  A^{^(m-2)} = 1/A  (mod m)    两边都余 m

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

#define MOD 9973

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        b%=MOD;
        int c = b;
        for (int i=0;i<MOD-3;i++)
            c = (c*b)%MOD;
        a = (a*c)%MOD;
        printf("%d
",a);
    }
    return 0;
}

 还可以用扩展欧几里得求逆元，a*x = 1 (mod m) , x 是 a 的逆元，然后，方程等价于 a*x + m*y = 1 (mod m)，扩展欧几里得可求得 x0 ，((x0% m)+m)%m 就是最小整数解

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
using namespace std;
#define MOD 9973

int exgcd(int a,int b,int &x,int &y)
{
    if (b==0)
    {
        x=1;
        y=0;
        return a;
    }
    int r = exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return r;
}

int main()
{
    int T;
    cin>>T;
    while (T--)
    {
        int a,b;
        cin>>a>>b;
        int x,y;
        int r = exgcd(b,MOD,x,y);
        x=(x%MOD+MOD)%MOD;
        cout<<a*x%MOD<<endl;
    }
    return 0;
}