西电oj1066 费马小定理

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