[CQBZOJ 3333] 洗牌机

题目大意

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);
    }
}