【题解】上帝与集合的正确用法 LUOGU P4139 欧拉降幂 —B_Z_B_Y

让我们愉悦的学习 QVQ

首先我们知道 ： (关于数学的题目，只要你知道公式，什么题都和（普及）差不多 QWQ)~~~

欧拉函数：phi（n）的定义为是小于或等于 n 的正整数中与 n 互质的数的数目（φ(1)=1）
1.$phi(a*b) = phi(a) * phi(b)$ (a,b 互质)

2.$phi(p)=p-1$

3.$phi(i * p)=p * phi(i) ~~~ (i~mod~p==0)$

4.$phi(i * p) = phi(i) * (p-1)~~~~ (i~mod~p~!=0)$

.

本题题意即上述定理：求 $a^b~mod~c~$可以转化为 a^($~b~mod~phi(~c~)+phi(~c~))~mod~c$

注意当 $phi(c)==1$ 时返回 0；

int solve(int mods){
    if(mods==1) return 0;
    int ok=phi(mods);
    return pows(2,solve(ok)+ok,mods);//这里只是求无限的 2^2^2^2...%p
}

主代码

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdlib>
using namespace std;

#define ll long long
#define fors(i,a,b) for(int i=(a);i<=(b);++i)
#define ford(i,a,b) for(int i=(a);i>=(b);--i)
const int Size=1<<25;
inline char getch(){
    static char buf[Size],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,Size,stdin),p1==p2) ? EOF : *p1++;
}
int read(){
    int s=0,flag=1;
    char c=getch();
    while(c>'9' || c<'0'){if(c=='-') flag=-1;c=getch();}
    while(c<='9' && c>='0'){s=(s<<1)+(s<<3)+c-'0';c=getch();}
    return s*flag;
}
void write(int x){
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
//以上皆为卡常
const int p=10000001;
int phi[p],vis[p],prime[p];
int OL(int n) {
    int x=sqrt(n+0.5),ans=n;
    fors(i,2,x)
        if(n%i==0) {
            ans=ans/i*(i-1);
            while(n%i==0) n/=i;//分解 n
        }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}//求单个数的欧拉函数

int mul(int a,int b,int p){
    a %= p , b %= p;
    return (a * b - (LL)(((long double) a * b + 0.5) / p ) * p + p) % p;
}// 快速乘（防止报精度

int pows(int a,int b,int mods){
    int ret=1;
    while(b){
        if(b&1)
            ret=mul(ret,a,mods);
        b>>=1;
        a=mul(a,a,mods);
    }
    return ret;
}
int solve(int mods){
    if(mods==1) return 0;
    int ok=OL(mods);
    return pows(2,solve(ok)+ok,mods);
}//递归求解
int a;
int main(int argc, char const *argv[])
{
    int t=read();
    fors(i,1,t){
        a=read();
        write(solve(a)),putchar(10);
    }
    return 0;
}