BZOJ 3884神と集合の正しい使い方(オラの定理)
5508 ワード
2^(2^(2^(2^(2^…))を求めます.mod pの値
問題:https://blog.csdn.net/popoqqq/article/details/43951401
転載先:https://www.cnblogs.com/Fy1999/p/9767524.html
問題:https://blog.csdn.net/popoqqq/article/details/43951401
#include
#include
#include
#define ll long long
using namespace std;
void read(int &k)
{
int f=1;k=0;char c=getchar();
while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();
k*=f;
}
ll phi(ll n)
{
ll rea=n;
for(int i=2;i*i<=n;i++)
{
if(n%i==0){
rea=rea-rea/i;
do
n/=i;
while(n%i==0);
}
}
if(n>1)
rea=rea-rea/n;
return rea;
}
ll quick_mod(ll a,ll b,ll c)
{
ll res,t;
res=1;
t=a%c;
while(b)
{
if(b&1){
res=res*t%c;
}
t=t*t%c;
b>>=1;
}
return res;
}
int T;
int p;
int Solve(int p)
{
if(p==1) return 0;
int temp=0;
//p=2^k*q;
while(~p&1) p>>=1,++temp;//p q,temp 2
int phi_p=phi(p);
int re=Solve(phi_p);//
(re+=phi_p-temp%phi_p)%=phi_p;
re=quick_mod(2,re,p)%p;
return p;
}
int main()
{
read(T);
while(T--){
read(p);
cout<endl;
}
return 0;
}
転載先:https://www.cnblogs.com/Fy1999/p/9767524.html