欧拉

φ(n)

欧拉函数，指的就是小于n与n互质的数的个数。
$$
φ(x)=x(1-\frac{1}{p_1})(1-\frac{1}{p_2})(1-\frac{1}{p_3})…(1-\frac{1}{p_n})，其中p_i为x的质因子
$$

int phi(int n) {
    int ans = n;
    for (int i = 2; i <= sqrt(n); ++i) if (n % i == 0) {
        ans = ans / i * (i-1);
        while (n % i == 0) n /= i;
    }
    if (n > 1) ans = ans / n * (n-1);
    return ans;
}

以下的代码以 O(NlogN)复杂度求出 [2,N] 中每个数的欧拉函数。

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

下面利用线性筛法的思想在 O(N)的时间内快速递推出 [2,N] 中每个数的欧拉函数。

typedef long long ll;
const int maxn = 10000000 + 5;
int phi[maxn], pri[1000005], n, tot;
bool mark[maxn];
ll ans, sum[maxn];
void getphi() {
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!mark[i]) { phi[i] = i - 1; pri[++tot] = i; }
        for (int j = 1; j <= tot; j++) {
            int x = pri[j];
            if (i*x>n)break;
            mark[i*x] = 1;
            if (i%x == 0) { phi[i*x] = phi[i] * x; break; }
            else phi[i*x] = phi[i] * phi[x];
        }
    }
}

降幂

公式

$$ a^x\equiv a^{x \ mod \ \phi(p) + \phi(p)} (mod \ p)\ (x \geq p) $$

快速幂

ll qmod(ll a,ll n,ll mod)
{
    ll b=a%mod,ans=1;
    while(n)
    {
        if(n&1)
        {
            ans=(ans*b)%mod;
        }
        b=b*b%mod;
        n>>=1;
    }
    return ans;
}

模板

#include<iostream>
#include<cstring>
using namespace std;

typedef __int64 ll;
char b[1000006];

ll ouler(ll n)
{
    ll ans=n,a=n;
    for(ll i=2;i*i<=a;i++){
        if(a%i==0){
            ans-=ans/i;
            while(a%i==0){
                a/=i;
            }
        }
    }
    if(a>1){
        ans-=ans/a;
    }
    return ans;
}

ll qmod(ll a,ll n,ll mod)
{
    ll tmp=a%mod,ans=1;
    while(n){
        if(n&1){
            ans=(ans*tmp)%mod;
        }
        tmp=tmp*tmp%mod;
        n>>=1;
    }
    return ans;
}
//利用公式
ll solve(ll a,char *b,ll c)
{
    int PHI=ouler(c);
    ll res=0;
    for(int i=0;b[i];i++)
    {
        res=(res*10+b[i]-'0');
        if(res>c)break;
    }
    if(res<=PHI)
    {
        return qmod(a,res,c);
    }
    else
    {
        res=0;
        for(int i=0;b[i];i++)
        {
            res=(res*10+b[i]-'0')%PHI;
        }
        return qmod(a,res+PHI,c);
    }
}

int main()
{
    ll a,c,i;
    ll n=0,tmp;
    while(scanf("%I64d%s%I64d",&a,b,&c)!=EOF)
    {
        printf("%I64d\n",solve(a,b,c));
    }
    return 0;
}