扩展欧几里德+快速幂
每次转换位置：第x位的转移到2*x %(n+1)这个位置上
那么m次后就到了(2^m)*x %(n+1)这个位置上
那么找洗牌m次后在 l 位置上的牌就相当于解线性模方程： (2^m)*x ≡ l (mod n+1) 扩展欧几里得即可
这里扩展欧几里得解的是ax+by=d(mod n+1) 的解，不是等于 l 的……不过只需x*l/d即可～
/**************************************************************
Problem: 1965
User: Tunix
Language: C++
Result: Accepted
Time:0 ms
Memory:1272 kb
****************************************************************/ //BZOJ 1965
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
/*******************template********************/
typedef long long LL;
LL n,m,l,x,y;
LL pow(LL x){
LL ans=,base=;
while(x){
if(x&) ans=(ans*base)%(n+);
base=base*base%(n+);
x>>=;
}
return ans;
}
void exgcd(LL a,LL b,LL &d,LL &x, LL &y){
if (!b) {d=a; x=; y=; return;}
else{ exgcd(b,a%b,d,y,x); y-=x*(a/b);}
}
int main(){
scanf("%lld%lld%lld",&n,&m,&l);
LL a=pow(m),b=n+,d;
exgcd(a,b,d,x,y);
x=(x*l/d)%b;
while(x<) x+=b;
printf("%lld\n",x);
return ;
}