题目大意
2n张牌放在2n个从1到2n的有序位置上。洗牌机每次可以把第i张牌洗到p(i)的位置上。P(i)的定义如下:
问经过最少多少轮洗牌,才会使所有牌回到原来的位置。
解题报告
老样子,测试数据福利
Input:
183511
94612
311
25
Output:
14076
12180
33
8
这题。。首先发现题目的函数化简一下,设X为第X张牌,答案为y,那么就变成了
$$ X*2^y \equiv X \pmod {2n+1}$$
变成
$$ 2^y \equiv 1 \pmod {2n+1}$$
很显然2^y是和2n+1互质的,那么根据欧拉定理有
$$ 2^{\varphi(2n+1)} \equiv 1 \pmod {2n+1}$$
那么肯定满足条件的最小y是phi(2n+1)的一个因子(这样的话y可以循环重叠(2n+1)/y次来满足上式)。
接着发现phi(2n+1)的因子最多只有2*根号phi(2n+1)个,枚举每个因子再用快速幂检验就可以了。
喂个代码~
代码
匆忙码出来的有点乱见谅。。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <climits>
#include <cmath>
typedef long long LL;
LL caltEular (LL val) {
int r = sqrt(val);
LL ans = 1;
for(int i = 2; i<=r; i++)
if(val % i == 0) {
ans *= i-1; val /= i;
while(val % i == 0) val /= i, ans *= i;
}
if(val != 1) ans *= val-1;
return ans;
}
#include <iostream>
inline LL advPow (LL a, int b, LL c) {
a %= c;
LL ret = 1;
while(b) {
if(b & 1) ret *= a, ret %= c;
a *= a, a %= c;
b >>= 1;
}
return ret%c;
}
int main () {
LL n;
while(~scanf("%I64d", &n)) {
if(n == 1) {puts("2"); continue ;}
LL phi = caltEular(2LL*n+1);
int r = sqrt(phi+1);
LL ans = 9999999999LL;
for(int i = 1; i<=std :: min((LL)r, ans); i++)
if(phi % i == 0) {
if(advPow(2, i, 2LL*n+1) == 1) ans = std :: min(ans, (LL)i);
if(advPow(2, phi/i, 2LL*n+1) == 1) ans = std :: min(ans, phi/i);
}
printf("%I64d\n", ans);
}
}
Join the discussion