HDU 1576:A/B (乘法逆元)

A/B

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

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)%m时,我们可以转化为(a%(b*m))/b,但从题目来看这种解法并不可行。

逆元:满足a*k≡1(mod)p的k值就是a关于p的乘法逆元。

当我们要求 (a/b)%p 的值,且a很大,无法直接求得a/b的值时,我们就要用到乘法逆元。
我们可以通过求b关于p的乘法逆元k,然后 (a*k)%p ,与 (a/b)%p是等价的。
因为9973是素数,所以我们可以采用费马小定理来求解逆元。

费马小定理:
  在p是素数的情况下,对任意整数x都有x^p≡x(mod p)
  如果x无法被p整除,则有x^(p−1)≡1(mod p)
  可以在p为素数的情况下求出一个数的逆元,x*x^(p−2)≡1(mod p),x^(p−2)即为逆元。

 

AC代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

#define mod 9973
typedef __int64 ll;

ll mult(ll a,ll n)  //求a^n%mod
{
    ll s=1;
    while(n)
    {
        if(n&1)s=s*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return s;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll n,b;
        scanf("%I64d%I64d",&n,&b);
        printf("%I64d\n",(n*mult(b,9973-2))%mod);
    }
    return 0;
}