杂题

题意

对于任意偶数(n)，一个长度为(n)的排列({p_i})，定义一次变换为：(p'_i=p_{i/2}(i~is~even),p'_i=p_{(i+n+1)/2}(i~is~odd))，若经过恰好(n)次变换第一次返回原排列，则(f(n)=n)，否则为(0)。
给定(N)，求(sumlimits_{i=1,i~is~even}^N f(i))
(Nle 10^7)

做法

结论0：(p'_{i}=p_{i/2(mod~n+1)})，或者说(p'_{2i(mod~n+1)}=p_i)
结论1：若经过(k)次变换返回原排列，则(2^kequiv 1(mod~n+1))

证明：
(2^kequiv 1(mod~n+1))等价于(r2^kequiv r(mod~n+1))

根据欧拉定理，(2^{phi(n+1)}equiv 1(mod~n+1))，故(kle phi(n+1)(k|phi(n+1)))，若(n+1)不为质数，(phi(n+1)<n)，一定不合法
考虑(n+1)为质数的情况，此时需要验证所有(phi(n+1)=n)的因子(x(x|n))是否全部不满足(2^xequiv 1(mod~n+1))

结论2：若存在(x|n,x eq n)，满足(2^xequiv 1(mod~n+1))，令(n=prodlimits_{i=1}^m p_i^{k_i})，则存在(y=frac{n}{p_i}(p_iin prime,p_i|n))满足(2^yequiv 1(mod~n+1))

通过线性筛将满足(n+1in prime)的(n)的质因子找到。这部分(O(pi(N)logN))
验证每个质因子，由于(nle 10^7)，最多有(8)个质因子。这部分(O(8pi(N)logN))