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      

  對于這道題，題目給出gcd(B, 9973)=1即互質，又9973為質數，是以可以看出此處用到費馬小定理。

由a=1(mod p),可以知道a^(p-1)=1(mod p)于是有a^(-1)=a^(p-2) (mod p)兩邊同除以a得到。

完整代碼：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long ll;
ll a,b;
ll s_mi(ll x, ll y, ll mod)
{
    x%=mod;
    //int k=0;
    ll ans=0;
    /*while(y)
    {
        int t=y&1;      //第k位上是否有1？
        ll temp=1;
        y=y>>1;
        if(t)
        {
            for(int i=1; i<=k; i++)
            {
                temp=(temp*(x*x)%mod)%mod;
            }
        }
        ans=(ans+temp)%mod;
        k++;        //放在最尾使得幂次從0開始
    }*/
    ans=x;
    for(int i=1; i<y; i++)
    {
        ans=(ans%mod*x%mod)%mod;
    }
    return ans;
}
int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%lld%lld",&a,&b);
        printf("%lld\n",(a*s_mi(b, 9971, 9973))%9973);
    }
    return 0;
}