@OceanEye7年前
05/12
17:25
降幂大法:-D
安利Tangjz题解
出题人的题解也是很强的qwq
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <cstdlib> #include <map> #include <iostream> #define ll long long #define INF 1000000000 #define p(x) ('0'<=x&&x<='9') char cc; int C; template <class T> void read( T &x ) { x=0; cc=getchar(); C=1; while(!p(cc)) { if(cc=='-') C=-1; cc=getchar(); } while(p(cc)) { x=x*10+cc-48; cc=getchar(); } x*=C; } using namespace std; int k; map<int,int> f; int ksm(int x,int a,int mod) { ll ret=1; for(;a;a>>=1) { if(a&1) ret=ret*x%mod; x=(ll)x*x%mod; } return (int)ret; } int calc_phi(int x) { int ret=x; for(int i=2;i*i<=x;i++) if(x%i==0) { ret-=ret/i; while(x%i==0) x/=i; } if(x>1) ret-=ret/x; return ret; } int solve(int p) { if(f.count(p)) return f[p]; int phi=calc_phi(p); return f[p]=ksm(2,solve(phi)+phi,p); } int T; int main() { f[1]=0; for(read(T);T;T--) { read(k); printf("%d\n",solve(k)); } return 0; } |