gmoj 6832. 2020.10.24【NOIP提高A组】T2.world

Solution

30pts

可以发现，第 i 个位置的数经过一次变换后会到达第 2i mod (n + 1) 的位置，假如 长度为 n 的序列经过 k 次变换后，第一个位置的数回到了第一个位置上，

那么就有 2^k ≡ 1 (mod (n + 1)) 对于其他任何一个位置的数就有 i ∗ 2^k ≡ i (mod (n + 1)) 因此，如果第一个数回到了第一个位置，那么其它数也会归位，就得到了初始排列。

所以我们只需要枚举第一个数就好了。时间复杂度 O(n² )。

40pts

观察上面出现过的式子 2^k ≡ 1 (mod (n + 1)) 由于要经过 n 次变换后恰好首次回到初始排列，那么 n 就是满足上述式子中最小 的 k。

由欧拉定理可以得到 2^ϕ(n+1) ≡ 1 (mod (n + 1)) 如果 n + 1 不是质数，那么 ϕ(n + 1) 就会小于 n，此时 n 就一定不是最小的 k 了。

所以只有当 n + 1 是质数时，我们才去判断 n。时间复杂度 O( n 2 logn)。

50 or 60pts

由于上面几个做法中，判断过程都是 O(n) 的，效率极其低下，因此考虑优化。 回顾判断过程： 我们想知道下列式子中 n 是否为最小满足条件的 k 使2^k ≡ 1 (mod (n + 1)) ，由于 n + 1 是个质数，

所以 n 一定满足上述式子。如果最小的 k 不是 n，那么这个 最小的 k 一定是 n 的约数。因此我们枚举 n 的约数，然后快速幂判断即可。判断个数 为 O( n logn)，约数个数均摊为 O(logn)，

快速幂为 O(logn)，总复杂度就是 O(nlogn) 了。

100pts

判断过程可以进一步优化。 2 把 n 质因数分解得到 n = p1^q1 * p2^q2 ...* pt^qt ，如果最小的 k 不是 n，由于 k 是 n 的 约数，那么 k 就是 n/p1 , n/p2 , ..., n/pt 其中至少一个数的约数，

即这些数中有至少一个满足 2^n/pi ≡ 1 (mod (n + 1))。也就是说，我们只需要枚举 n 的所有质因数就好了。

不同于约数个数，在 10⁷ 范围内，不同的质因数个数最多的数也仅仅只有 8 个，其 它的数则远远达不到这个值。

因此，在完全算满的情况下，判断个数为 O( n logn)，质因 数个数为 O(8)，快速幂为 O(logn)，总复杂度也仅仅只有 O(8n)，足以通过所有数据。

Code

#include<cstdio>
#define ll long long
using namespace std;

const int N=1e7+10;
int su[N],a[N],bz[N];
int n,P,m,i; ll an;

inline void pre(){
    int i,j;
    for(i=2;i<=n+1;++i){
        if (!bz[i]) su[++P]=i;
        for(j=1;j<=P&&i*su[j]<=n+1;++j){
            bz[i*su[j]]=1;
            a[i*su[j]]=su[j];
            if (i%su[j]==0) break;
        }
    }
}
inline int ksm(int x,int y,int mo){
    int s=1;
    while(y){
        if (y&1) s=1ll*s*x%mo;
        x=1ll*x*x%mo; y>>=1;
    }
    return s;
}
inline int pd(int x){
    int y=x;
    while(a[x]){
        if (ksm(2,y/a[x],y+1)==1) return 0;
        int z=a[x];
        while(x%z==0) x/=z;
    }
    
    if (x>1&&ksm(2,y/x,y+1)==1) return 0;
    return 1;
}
int main(){
    freopen("world.in","r",stdin);
    freopen("world.out","w",stdout);
    scanf("%d",&n); pre();
    for(i=2;i<=P;++i){
        m=su[i]-1;
        if (pd(m)) an+=m;
    }
    printf("%.5lf",1.0*an*2/n);
    return 0;
}

转载自gmoj题解。