指数循环节

A - Super A^B mod C

这题的关键是要知道$$a^b \equiv a^{b \% \phi(c)+\phi(c)}(mod \ c),b>\phi(c) $$

这个公式就行。本题最大的难点就是我们要用数组处理这个B，太大了。本题数据水，忽略后面的条件也是可以过的

B - CalculationHDU - 2837

本题有指数的指数的…次方。对于模数，我们提前打一个表然后倒着跑，如果满足条件利用公式，不满足的我们直接计算。

#include<cstdio>
#include<iostream>
#include<cmath>
#define ll long long
using namespace std;
ll n, m;
ll quickmod(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;
}

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

ll slove(ll a, ll b, ll c){
    if(b*log(a) >= log(c))
        return quickmod(a,b,c)+c;
    else return quickmod(a, b, c);
}

char s[20];
int mod[20];
int t;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        mod[0] = m;
        for(int i = 1; i < 10; i++){
            mod[i] = phi(mod[i-1]);
        }
        int cont = 0;

        while(n){
            s[cont++] = n%10;
            n /= 10;
        }
        ll ans = 1;
        for(int i = cont - 1; i >= 0; i--){
            ans = slove(s[i], ans, mod[i]);
        }
        printf("%lld\n",ans%m);
    }
    return 0;
}

C - What is N?

这里$$n^{n!} \equiv b(mod \ p)$$有多少个成立的n，对于指数%phi(p)为0后的数，是存在循环节的。只要记录一下一次循环的个数p，最后多余的部分去跑一下记忆化的就知道有多少组了。

#include<cstdio>
#include<iostream>
#include<cmath>
#define ll unsigned long long
const int maxn = 1e5+5;
using namespace std;

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

ll quickmod(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;
}
ll b, p, m, fa[maxn];
int main(){
    int t=0,T;scanf("%d",&T);
    while(t++<T){
        scanf("%I64u%I64u%I64u", &b, &p, &m);
        printf("Case #%d: ",t);
        if(p==1){
            if(m==18446744073709551615ull)
                printf("18446744073709551616\n");
            else printf("%I64u\n",m+1);
            continue;
        }else{
            ll i = 0;
            ll phic = phi(p);
            ll fac = 1;
            ll ans = 0;

            for(i = 0; i <= m && fac<=phic; i++){
                if(quickmod(i, fac, p) == b){
                    ans ++;
                }
                fac *= i+1;
            }
            fac = fac%phic;
            ///until
            for(;i <= m && fac; i++){
                if(quickmod(i, fac + phic, p) == b){
                    ans++;
                }
                fac = (fac*(i+1))%phic;
            }
            if(i <= m){
                ll cnt = 0;
                for(int j = 0; j < p; j++){
                    fa[j] = quickmod(i+j, phic, p);
                    if(fa[j] == b){
                        cnt ++;
                    }
                }
                ll idx = (m-i+1)/p;
                ans += cnt * idx;
                ll remain = (m-i+1)%p;
                for(int j = 0; j < remain; j++){
                    if(fa[j] == b)
                        ans ++ ;
                }
            }
            printf("%I64u\n",ans);
        }
    }
    return 0;
}