西电oj1066 费马小定理

问题 A: A^B % P

时间限制: 1 Sec  内存限制: 128 MB
提交: 28  解决: 8
[提交][状态][讨论版]

题目描述

 

输入

 

输出

 

样例输入

2 3 1 2 2 2 2

样例输出

9 64

思路：先求k=B0*B1*...*Bn-1%(p-1),最后算出A^k%p即为答案。
　　　　依据：由费马小定理，若a,p互质，a^(p-1)=1(mod p);因此，A^(B0*B1*...*Bn-1)%p=A^((p-1)的倍数+((B0*B1*...*Bn-1)%(p-1)))%p=(A^(p-1)的倍数%p)*((A^k)%p)=1*((A^k)%p)=A^k%p; #include<bits/stdc++.h>using namespace std;const int maxn=10100; const int INF=(1<<29); typedef long long ll; const ll p=1000000000+7;int T; ll A,B0,n;ll qpow(ll n,ll k) {ll res=1;while(k){if(k&1) res=(res%p)*(n%p);n=(n%p)*(n%p);k>>=1;}return res; }ll s(ll x,ll p) {ll res=1;p--;for(int i=0;i<=n-1;i++){res=(res%p)*(x%p)%p;x=((x%p)*(x%p)+p-1)%p;}return res; }int main() {cin>>T;while(T--){cin>>A>>n>>B0;ll k=s(B0,p);ll ans=qpow(A,k);cout<<ans%p<<endl;}return 0; } View Code

 

转载于:https://www.cnblogs.com/--560/p/4539174.html

总结

以上是生活随笔为你收集整理的西电oj1066 费马小定理的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。