從圖中可以看出經(jīng)過一次洗牌，序列1 2 3 4 5 6變?yōu)? 1 5 2 6 3。當(dāng)然，再對得到的序列進行一次洗牌，又會變?yōu)? 4 6 1 3 5。 游戲是這樣的，如果給定長度為N的一疊撲克牌，并且牌面大小從1開始連續(xù)增加到N（不考慮花色），對這樣的一疊撲克牌，進行M次洗牌。最先說出經(jīng)過洗牌后的撲克牌序列中第L張撲克牌的牌面大小是多少的科學(xué)家得勝。小聯(lián)想贏取游戲的勝利，你能幫助他嗎？Day1
題解：快速冪
其實是道規(guī)律題啦。
一次洗牌之后位置x會變換到位置2*x%(n+1)
所以x*(2^m)=L (mod n+1)
2是偶數(shù)，n+1是奇數(shù)，所以兩者一定互質(zhì)，2^m也一定與n+1互質(zhì)。
我們其實只需要知道2在模n+1意義下的的逆元，2*x+(n+1)*y=1 x的最小正整數(shù)解就是當(dāng)y=-1時，x=n/2+1
所以這道題的答案就是(n/2+1)^m*L %(n+1)
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define LL long long using namespace std;LL n,m,l;LL quickpow(LL num,LL x,LL p){ LL base=num%p; LL ans=1; while (x) { if (x&1) ans=ans*base%p; x>>=1; base=base*base%p; } return ans;}int main(){ cin>>n>>m>>l; PRintf("%I64d/n",quickpow(n/2+1,m,n+1)*l%(n+1));}
新聞熱點
疑難解答
