Description 根據一些書上的記載，上帝的一次失敗的創世經歷是這樣的： 第一天， 上帝創造了一個世界的基本元素，稱做“元”。 第二天， 上帝創造了一個新的元素，稱作“α”。“α”被定義為“元”構成的集合。容易發現，一共有兩種不同的“α”。 第三天， 上帝又創造了一個新的元素，稱作“β”。“β ...
Submit: 3860 Solved: 1751
[Submit][Status][Discuss]
Description
根據一些書上的記載，上帝的一次失敗的創世經歷是這樣的： 第一天， 上帝創造了一個世界的基本元素，稱做“元”。 第二天， 上帝創造了一個新的元素，稱作“α”。“α”被定義為“元”構成的集合。容易發現，一共有兩種不同的“α”。 第三天， 上帝又創造了一個新的元素，稱作“β”。“β”被定義為“α”構成的集合。容易發現，一共有四種不同的“β”。 第四天， 上帝創造了新的元素“γ”，“γ”被定義為“β”的集合。顯然，一共會有16種不同的“γ”。 如果按照這樣下去，上帝創造的第四種元素將會有65536種，第五種元素將會有2^65536種。這將會是一個天文數字。 然而，上帝並沒有預料到元素種類數的增長是如此的迅速。他想要讓世界的元素豐富起來，因此，日復一日，年復一年，他重覆地創造著新的元素…… 然而不久，當上帝創造出最後一種元素“θ”時，他發現這世界的元素實在是太多了，以致於世界的容量不足，無法承受。因此在這一天，上帝毀滅了世界。 至今，上帝仍記得那次失敗的創世經歷，現在他想問問你，他最後一次創造的元素“θ”一共有多少種？ 上帝覺得這個數字可能過於巨大而無法表示出來，因此你只需要回答這個數對p取模後的值即可。 你可以認為上帝從“α”到“θ”一共創造了10^9次元素，或10^18次，或者乾脆∞次。 一句話題意：
Input
接下來T行，每行一個正整數p，代表你需要取模的值
Output
T行，每行一個正整數，為答案對p取模後的值
Sample Input
32
3
6
Sample Output
01
4
HINT
對於100%的數據，T<=1000,p<=10^7
Source
擴展歐拉定理$a^p \equiv a^{p \% \phi(M) + \phi(M)} \pmod {M}$
歐拉函數：1. 當$N > 3$時，$\phi(N)$為偶數
2.若$N$為偶數，則$\phi(N) <= \frac{N}{2}$
然後直接暴力算就行了，很顯然不會超過$logp$層
#include<cstdio> #include<map> #include<cstring> using namespace std; const int MAXN = 1e7 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar(); return x * f; } int mp[MAXN]; int GetPhi(int x) { int ans = x; for(int i = 2; i * i <= x; i++) { if(!(x % i)) { ans = ans / i * (i - 1); while(!(x % i)) x /= i; } } if(x > 1) ans = ans / x * (x - 1); return ans; } int fastpow(int a, int p, int mod) { int base = 1; while(p) { if(p & 1) base = (1ll * base * a) % mod; a = (1ll * a * a) % mod; p >>= 1; } return base % mod; } int F(int mod) { if(mp[mod] != -1) return mp[mod]; int phi = GetPhi(mod); return mp[mod] = fastpow(2, F(phi) + phi, mod); } int main() { memset(mp, -1, sizeof(mp)); int QwQ = read(); mp[1] = 0; while(QwQ--) { int mod = read(); printf("%d\n", F(mod)); //printf("%d\n", GetPhi(mod)); } return 0; }
