题解 P1405 【苦恼的小明】

神一般的世界 · 2016-08-30 20:05:57 · 题解

话说这是一道正宗的数论题

前几个点都比较水一个快速幂

然后才是这道题的本体

果断费马小定理

a^(φ(m))≡1(mod m) ((a,m)=1)

phi(m)为欧拉函数（先打表筛欧拉函数）

于是得(a^b)mod m=(a^(b%phi(m)))mod m

但是在下苦于才疏学浅，不知若是a与m不互质时怎么证明，有大神的话可以私信教我

附上代码

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
const int pp=10007;
const int NN=10010;
int a[2000000];
int phi[NN],vis[NN],prime[NN];
int ans,tot,n;
int gphi(){//这是个欧拉函数 
    phi[1]=1;
    for(int i=2;i<=NN;i++){
        if(!vis[i]){
            prime[++tot]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=tot;j++){
            if(i*prime[j]>NN)break;
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
            }
            else{
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
}
int qpow(int a,int k,int p){//quick pow 水 
    if(k==0)return 1;
    int t=qpow(a,k/2,p)%p;
    t=(t*t)%p;
    if(k&1)t=(t*a)%p;
    return t;
}
int modex(int k,int x){//a^b mod m=a^(b mod phi(m)) mod m  
    if(x==n)return a[x]%k;
    int kt=modex(phi[k],x+1);
    int tt=qpow(a[x],kt,k);
    //cout<<a[x]<<' '<<kt<<' '<<k<<' '<<tt<<endl;
    return tt;
}
int main(){
    gphi();
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    ans=modex(pp,1);
    printf("%d",ans);//好神奇竟然过了
    return 0;
}