1 //phi(a)=a*(a1-1)*(a2-1)*(a3-1)*...*(an-1)/(a1*a2*a3*...*an); 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 typedef __int64 LL; 8 LL phi(LL a){//phi 9     LL temp=a;10     for(LL i=2;i*i<=a;i++)11         if(a%i==0){12             while(a%i==0)  a/=i;13             temp=temp/i*(i-1);14         //    cout<<"a="<<a<<" i="<<i<<endl;15         }16         //cout<<"a="<<a<<endl;17         if(a!=1)  temp=temp/a*(a-1);18     return temp;19 }20 int main(){21     LL a;22     while(cin>>a)23     cout<<"phi(a)="<<phi(a)<<endl;24     return 0;25 }
快速乘方 求a的k次方mod b

 1 #include<iostream> 2 #include<cstdlib> 3 #include<cstring> 4 using namespace std; 5 typedef __int64 LL; 6 LL modd(LL a,LL k,LL b){ 7     int temp,ans; 8     ans=1; 9     temp=a;10     while(k!=0){11         if(k%2)   ans=ans*temp%b;12         temp=temp*temp%b;13         k/=2;14     }15     return ans;16 }17 int main(){18     LL a,b,k;19     while(cin>>a>>b>>k)20       cout<<modd(a,k,b)<<endl;21     return 0;22 }