欧拉函数

欧拉函数：求小于等于n的数中与n互质的数的数量

求欧拉函数值：

ll euler(ll x) {
    ll ans=x;
    for(int i=2;i*i<=x;i++) {
        if(x%i==0) {
            ans=(ans/i)*(i-1);
            while(x%i==0) x/=i;
        } 
    }
    if(x>1) ans=(ans/x)*(x-1);
    return ans; 
}

预处理欧拉函数值：

void init( ) {
    for(int i=1;i<=maxn;i++) euler[i]=i;
    for(int i=2;i<=maxn;i++) {
        if(euler[i]==i) {
            for(int j=i;j<=maxn;j+=i) 
            euler[j]=euler[j]/i*(i-1);
        }
    }
}

应用：欧拉降幂

例题：https://vjudge.net/problem/FZU-1759

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
#define maxn 1000050
ll a,c,ec;
char b[maxn];

ll euler(ll x) {
    ll ans=x;
    for(int i=2;i*i<=x;i++) {
        if(x%i==0) {
            ans=(ans/i)*(i-1);
            while(x%i==0) x/=i;
        } 
    }
    if(x>1) ans=(ans/x)*(x-1);
    return ans; 
}

ll power(ll a,ll b,ll c) {
    ll ans=1;
    while(b) {
        if(b&1) ans=ans*a%c;
        a=a*a%c;
        b>>=1;
    }
    return ans%c;
}
int main( ) {
    while(~scanf("%lld%s%lld",&a,b,&c)) {
        ec=euler(c);
        int len=strlen(b);
        ll ans=0;
        for(int i=0;i<len;i++) {
            ans=(ans*10+(int)(b[i]-'0'));
            if(ans>c) break;
        }
        if(ans<=c) cout<<power(a,ans,c)<<endl;
        else {
            ans=0;
            for(int i=0;i<len;i++) ans=(ans*10+(int)(b[i]-'0'))%ec;
            ans+=ec;
            cout<<power(a,ans,c)<<endl;;
        }
    }
    return 0;
}