题目大意
求2222222...mod p的值。
分析
po姐的题目诶！！大意就是上面那样，看上去+∞个2根本不可做，不过有欧拉定理xa≡xa mod φ(p)+φ(p) (mod p)。那么我们有f(n)=2222222...(mod n)=2(222222... mod φ(n))+φ(n) (mod n)=2f(φ(n))+φ(n) (mod n)递归做下去即可，当n==1，返回0(任何数mod 1等于0)。欧拉函数建议直接算，递推不知道会不会TLE。
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
int t;
LL x;
LL phi(LL n){
LL tmp = n;
for(LL i=2;i*i<=n;i++)
if(n%i == 0){
tmp = tmp/i*(i-1);
while(n%i == 0) n /= i;
}
if(n > 1) tmp = tmp/n*(n-1);
return tmp;
}
LL pwr(LL n,LL k,LL p){
LL ans = 1;
while(k) {if(k&1) ans=(ans*n)%p;n=(n*n)%p;k>>=1;}
return ans;
}
LL f(LL p)
{
if(p==1) return 0;
LL phi_p=phi(p);
return pwr(2,f(phi_p)+phi_p,p);
}
int main(){
scanf("%d",&t);
while( t-- ){
scanf("%lld",&x);
PRintf("%lld\n",f(x));
}
return 0;
}
