UVA 10710 - Chinese Shuffle

题目链接

题意：给定n张牌，完美洗牌n - 1次，问是否会变回原来的序列

思路：完美洗牌：
假设有a1a2a3...anb1b2b3...bn的牌，设每张牌原来的位置为x，那么完美洗牌一次后，前n张牌分别到2 x位置，后n张分别到1, 3, 5..也就是2x % (2 n + 1)的位置，因此每张牌位置变为2 x % (2 * n + 1).这样去判断每张牌是否到原位就可以得出答案了，但是牌很多的情况根本无法判断，那怎么办呢？

其实只要判断第一张就可以了，证明：
假设完美洗牌p次，那么第一张牌位置为1 2^p % (2 n + 1) = 1，那么第x张牌的位置为x 2^p % (2 n + 1) = x就得得证了。

在来考虑这题，这题给定的完美洗牌方式，那么其实对于偶数就可以看成奇数的情况（因为第一张始终不变），然后和上面一样去推一下位置变化，最后得到每张牌的位置为x * 2^(n - 1) % n,这样一来带入1，问题就变成了判断2 ^ (n - 1) % n == 1，用快速幂即可

代码：

#include <stdio.h>
#include <string.h>

long long n;

long long pow_mod(long long x, long long k, long long mod) {
	if (k == 0) return 1;
	long long ans = pow_mod(x * x % mod, k>>1, mod);
	if (k&1) ans = ans * x % mod;
	return ans;
}

int main() {
	while (~scanf("%lld", &n) && n != -1) {
		if (pow_mod(2, n - 1, n) == 1)
			printf("%d is a Jimmy-number\n", n);
		else
			printf("%d is not a Jimmy-number\n", n);
 	}
	return 0;
}