BZOJ 1965 [Ahoi2005]SHUFFLE 洗牌

题目大意

给你n$(n \le 10^{10})$张牌，求通过特殊规律洗牌m$(m \le 10^{10})$之后第l张牌。

使用的公式：

费马小定理

$$a^{-1} = a^{\varphi(p)-1} (\mod p, \gcd(a,p) = 1)$$

$O(\sqrt{n})$求一个数的欧拉函数:

$$\varphi(n) = \prod\frac{p_i-1}{p_i}$$

容易发现洗牌模式是很特殊的——第i张牌在进行一次洗牌后会跑到$2i \mod (n+1)$这一位置。

所以式子就变成了求一个x使得$x \times 2^m = l (\mod (n+1))$

暴力除过去就行，之后求得$x = \frac{l}{2^m}$

求出$2^m$的逆元就可以得解了。

#include <cstdio>
#define R register
long long MO;
inline long long smul(R long long x,R long long y)
{
	R long long ret=0,tmp=x;
	for(R int i=0;1ll<<i<=y;++i)
	{
		if(1ll<<i&y) ret=(ret+tmp)%MO;
		tmp=(tmp+tmp)%MO;
	}
	return ret;
}
inline long long spow(R long long x,R long long y)
{
	R long long ret=1,tmp=x;
	for(R int i=0;1ll<<i<=y;++i)
	{
		if(1ll<<i&y) ret=smul(ret,tmp);
		tmp=smul(tmp,tmp);
	}
	return ret;
}
inline long long phi(R long long tg)
{
	R long long ret=tg;
	for(R long long i=2;i*i<=tg;++i)
		if(!(tg%i))
		{
			ret=ret/i*(i-1);
			while(!(tg%i)) tg/=i;
		}
	if(tg!=1) ret=ret/tg*(tg-1);
	return ret;
}
int main()
{
	R long long n,m,l;
	scanf("%lld%lld%lld",&n,&m,&l);
	MO=n+1;
	printf("%lld\n",smul(l,spow(spow(2,m),phi(MO)-1)));
	return 0;
}