A/B

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

2
1000 53
87 123456789

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;
}