from Exponial Kattis - exponial NCPC 2016

题意

求 n(n−1)n−2...%m

分析

欧拉函数降幂公式
A^B(mod m)=A^{B \% ψ(m)+ψ(m)} (B<=ψ(m))
对于n <= 5的直接暴力求，对于n >= 5 递归求解
同类题

参考代码

#include <iostream>
#include <cstdio>
using namespace std;
typedef  long long LL;
LL Euler(LL n)//欧拉函数
{
    LL ans = n;
    for(LL i = 2; i * i <= 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;
}
LL qpow(LL q,LL a,LL m)//快速幂
{
    LL ans = 1;
    q %= m;
    while(a > 0)
    {
        if(a&1)
            ans = ans * q % m;
        q = q*q % m;
        a >>= 1;
    }
    return ans;
}
long long ff(long long n,long long m)
{
    if(n % m == 0)
        return 0;
    if(n==5)
        return qpow(n,1<<18,m);
    if(n==4)
        return qpow(n,9,m);
    if(n==3)
        return qpow(n,2,m);
    if(n==2)
        return n % m;
    return 1;

}
long long f(long long n,long long m)
{
    if(n <= 5)
        return ff(n,m);
    if(n%m==0)
        return 0;
        return qpow(n,f(n-1,Euler(m))+Euler(m),m);
}

int main()
{
// cout<<(1<<18)<<endl;
    LL n,m;
    while(cin>>n>>m)
    {
       cout<<f(n,m)<<endl;
    }
    return 0;
}