欧拉函数&&快速乘方

 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 }