费马小定理(应用+拓展)

本文主要是介绍费马小定理(应用+拓展)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

费马小定理(应用+拓展)

定义：如果两个整数a,p互质，也就是gcd(a,p)=1,那么a^(p-1)≡1( mod p).

公式拓展一下
拓展公式1：n*a^(p-1)≡n(mod p)
拓展公式2：a^(p-2) ≡ a ^(-1) (mod p)
拓展公式3：a^b ≡ a^(bmod(p-1)) (mod p)

求(A/B)%999983，但由于A很大，我们只给出n(n=A%999983)(我们给定的A必能被B整除，且gcd(B,999983) = 1)。
Input

Input

数据的第一行是一个T，表示有T组数据。
每组数据有两个数n(0 <= n < 999983)和B(1 <= B <= 10^9)。

Output

对应每组数据输出(A/B)%999983。

Sample Input

2
1000 53
87 123456789

Sample Output
660385
801745

解题方法:由于A是一个巨大的数，所以题目中没有告诉你A的大小，而是告诉你了A%999983的值，怎么通过这个值求(A/B)%999983呢？

注意(A/B)%p=(A*B^(-1))%p
所以(A/B)≡(A * B^(-1)) (mod p)
由扩展公式2得到B^(p-2)≡B ^(-1) (mod p)
再由扩展公式1得到 A * B^(p-2)≡A * B ^(-1) (mod p)

所以用快速幂求出B^(p-2)%p，问题就得到解决

代码如下

#include<iostream>
using namespace std;
const int mod=999983;
typedef long long ll;
/*快速幂*/
ll pow_quick(ll dishu,ll zhishu)//dishu是底数，zhishu是指数 
{ll answer=1;while(zhishu!=0){if(zhishu&1)//zhishu%2==1{answer=answer*dishu%mod;zhishu--;}else{dishu=dishu*dishu%mod;zhishu/=2;}}answer=answer%mod;return answer;
}
int main()
{int t;scanf("%d",&t);while(t--){ll n,B;scanf("%lld %lld",&n,&B);ll ans=n*pow_quick(B,mod-2)%mod;printf("%lld\n",ans);}return 0;
}