題目描述

為了表彰小聯(lián)為Samuel星球的探險所做出的貢獻，小聯(lián)被邀請參加Samuel星球近距離載人探險活動。 由于Samuel星球相當遙遠，科學家們要在飛船中度過相當長的一段時間，小聯(lián)提議用撲克牌打發(fā)長途旅行中的無聊時間。玩了幾局之后，大家覺得單純玩撲克牌對于像他們這樣的高智商人才來說太簡單了。有人提出了撲克牌的一種新的玩法。 對于撲克牌的一次洗牌是這樣定義的，將一疊N（N為偶數(shù)）張撲克牌平均分成上下兩疊，取下面一疊的第一張作為新的一疊的第一張，然后取上面一疊的第一張作為新的一疊的第二張，再取下面一疊的第二張作為新的一疊的第三張……如此交替直到所有的牌取完。 如果對一疊6張的撲克牌1 2 3 4 5 6，進行一次洗牌的過程如下圖所示：??從圖中可以看出經(jīng)過一次洗牌，序列1 2 3 4 5 6變?yōu)? 1 5 2 6 3。當然，再對得到的序列進行一次洗牌，又會變?yōu)? 4 6 1 3 5。 游戲是這樣的，如果給定長度為N的一疊撲克牌，并且牌面大小從1開始連續(xù)增加到N（不考慮花色），對這樣的一疊撲克牌，進行M次洗牌。最先說出經(jīng)過洗牌后的撲克牌序列中第L張撲克牌的牌面大小是多少的科學家得勝。小聯(lián)想贏取游戲的勝利，你能幫助他嗎？

輸入

有三個用空格間隔的整數(shù)，分別表示N，M，L （其中0＜ N ≤ 10 ^ 10 ，0 ≤ M ≤ 10^ 10，且N為偶數(shù)）。

輸出

單行輸出指定的撲克牌的牌面大小。

樣例輸入

6 2 3

樣例輸出

6

---

題解

歐拉定理

由題意，第i張牌洗牌后的位置是2i mod (n+1)。

那么原題就是要求$2^m·x\equiv l\ \ \ (mod\ (n+1))$的最小正整數(shù)解 。

直接使用乘法逆元將$2^m$除過去即可。

注意到$2^m$與$n+1$一定是互質(zhì)的，因此由歐拉定理$a^{\varphi(p)}\equiv 1\ (mod\ p)$，可以求得$2^m$的逆元為$(2^m)^{\varphi(n+1)-1}$。

求一下歐拉函數(shù)并使用快速冪求解即可。

當然好像還有更快但是更麻煩的EXgcd算法

由于兩個大數(shù)相乘會爆long long，因此還要使用快（man）速乘

#include <cstdio> #include <algorithm> using namespace std; typedef long long ll; ll mul(ll x , ll y , ll mod) {ll ans = 0;while(y){if(y & 1) ans = (ans + x) % mod;x = (x + x) % mod , y >>= 1;}return ans; } ll pow(ll x , ll y , ll mod) {ll ans = 1;while(y){if(y & 1) ans = mul(ans , x , mod);x = mul(x , x , mod) , y >>= 1;}return ans; } ll phi(ll x) {ll ans = x , i;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; } int main() {ll n , m , l;scanf("%lld%lld%lld" , &n , &m , &l);printf("%lld\n" , mul(pow(pow(2 , m , n + 1) , phi(n + 1) - 1 , n + 1) , l , n + 1));return 0; }

?

?

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

總結(jié)

以上是生活随笔為你收集整理的【bzoj1965】 [Ahoi2005]SHUFFLE 洗牌 欧拉定理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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