让我们愉悦的学习 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 mods){
    int ret=0;
    while(b){
        if(b&1) ret=(ret+a)%mods;
        b>>=1;
        a=(a+a)%mods;
    }
    return ret;
}//为防止爆炸的乘
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;
}
分类: 文章

B_Z_B_Y

虽然也包含些许残酷 , 时间毕竟对任何人都很温柔-。---2018 NOIP 退役人士

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *