題目描述

根據(jù)一些書(shū)上的記載，上帝的一次失敗的創(chuàng)世經(jīng)歷是這樣的： 第一天， 上帝創(chuàng)造了一個(gè)世界的基本元素，稱做“元”。 第二天， 上帝創(chuàng)造了一個(gè)新的元素，稱作“α”。“α”被定義為“元”構(gòu)成的集合。容易發(fā)現(xiàn)，一共有兩種不同的“α”。 第三天， 上帝又創(chuàng)造了一個(gè)新的元素，稱作“β”。“β”被定義為“α”構(gòu)成的集合。容易發(fā)現(xiàn)，一共有四種不同的“β”。 第四天， 上帝創(chuàng)造了新的元素“γ”，“γ”被定義為“β”的集合。顯然，一共會(huì)有16種不同的“γ”。 如果按照這樣下去，上帝創(chuàng)造的第四種元素將會(huì)有65536種，第五種元素將會(huì)有2^65536種。這將會(huì)是一個(gè)天文數(shù)字。 然而，上帝并沒(méi)有預(yù)料到元素種類數(shù)的增長(zhǎng)是如此的迅速。他想要讓世界的元素豐富起來(lái)，因此，日復(fù)一日，年復(fù)一年，他重復(fù)地創(chuàng)造著新的元素…… 然而不久，當(dāng)上帝創(chuàng)造出最后一種元素“θ”時(shí)，他發(fā)現(xiàn)這世界的元素實(shí)在是太多了，以致于世界的容量不足，無(wú)法承受。因此在這一天，上帝毀滅了世界。 至今，上帝仍記得那次失敗的創(chuàng)世經(jīng)歷，現(xiàn)在他想問(wèn)問(wèn)你，他最后一次創(chuàng)造的元素“θ”一共有多少種？ 上帝覺(jué)得這個(gè)數(shù)字可能過(guò)于巨大而無(wú)法表示出來(lái)，因此你只需要回答這個(gè)數(shù)對(duì)p取模后的值即可。 你可以認(rèn)為上帝從“α”到“θ”一共創(chuàng)造了10^9次元素，或10^18次，或者干脆∞次。 一句話題意：

輸入

接下來(lái)T行，每行一個(gè)正整數(shù)p，代表你需要取模的值

輸出

T行，每行一個(gè)正整數(shù)，為答案對(duì)p取模后的值

樣例輸入

3
2
3
6

樣例輸出

0
1
4

---

題解

擴(kuò)展歐拉定理

內(nèi)容：

證明參考 https://zhuanlan.zhihu.com/p/24902174

這個(gè)定理不要求a和p互質(zhì)，可以直接使用。

回到題目中，設(shè)a=2，n=2^2^...，由于有無(wú)窮個(gè)2，,所以有a^n mod p = a^(a^n mod phi(p) + phi(p)) mod p。

可以發(fā)現(xiàn)a^n mod p和a^n mod phi(p)是一樣的，所以我們可以遞歸求解。

邊界條件：當(dāng)a^n mod p為定值時(shí)結(jié)束。我們可以知道當(dāng)p=1時(shí)這個(gè)式子必然等于0，可以結(jié)束。

而且這樣的方法時(shí)間復(fù)雜度是O(logp)的，參考 http://blog.csdn.net/popoqqq/article/details/43951401

這樣加上快速冪就能求解了。

#include <cstdio> #include <algorithm> using namespace std; typedef long long ll; ll pow(ll y , ll p) {ll x = 2 , ans = 1;while(y){if(y & 1) ans = ans * x % p;x = x * x % p , y >>= 1;}return ans; } ll phi(ll x) {ll i , ans = x;for(i = 2 ; i * i <= x ; i ++ ){if(x % i == 0){ans = ans / i * (i - 1);while(x % i == 0) x /= i;}}if(x != 1) ans = ans / x * (x - 1);return ans; } ll cal(ll p) {if(p == 1) return 0;ll t = phi(p);return pow(cal(t) + t , p); } int main() {int T;ll p;scanf("%d" , &T);while(T -- ) scanf("%lld" , &p) , printf("%lld\n" , cal(p));return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/GXZlegend/p/6950483.html

總結(jié)

以上是生活随笔為你收集整理的【bzoj3884】上帝与集合的正确用法 扩展欧拉定理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。