题意

题解

首先我们不竖着看奶牛而是横着看。从下往上把奶牛叫做处于第0,1,2...0,1,2...0,1,2...层。那么相当于第000层的不动，第111层的平移一格，第222层的平移222格，以此类推，第iii层平移iii格。假设每一层的最小正周期为xix_ixi，则显然有xi∣ix_i|ixi∣i且xi∣nx_i|nxi∣n。因为第iii层动了iii步恰好复原，iii就一定是最小正周期的倍数；因为是nnn的环排列，所以最小正周期是nnn的因数。

那么就有xi∣gcd(i,n)x_i|gcd(i,n)xi∣gcd(i,n)，又因为iii与i−1i-1i−1互质，则gcd(i,n)gcd(i,n)gcd(i,n)与gcd(i−1,n)gcd(i-1,n)gcd(i−1,n)互质，所以xix_ixi与xi−1x_{i-1}xi−1互质。

又因为为了不让第iii层的奶牛悬空，有第iii层的位置移动后必有第i−1i-1i−1层的奶牛支撑，结合互质得到，在xix_{i}xi存在的情况下，xi−1=1x_{i-1}=1xi−1=1。

意思就是说除了最上面一层，下面其它层周期均为111，也就是全都占满了，每一层都是nnn头奶牛。那么这个序列最多只能出现两个值，iii和i−1i-1i−1。

我们枚举iii，最大周期是gcd(i,n)gcd(i,n)gcd(i,n)，答案就是

1+∑i=1n−1(2gcd(i,n)−1)=(∑i=1n−12gcd(i,n))−(n−2)\large1+\sum_{i=1}^{n-1}\left(2^{gcd(i,n)}-1\right)=\left(\sum_{i=1}^{n-1}2^{gcd(i,n)}\right)-(n-2)1+i=1∑n−1(2gcd(i,n)−1)=⎝⎛i=1∑n−12gcd(i,n)⎠⎞−(n−2)前面的111表示最高层是第000层，后面的表示在gcd(i,n)gcd(i,n)gcd(i,n)这一最大周期内每个值只有iii和i−1i-1i−1两种取法，所以是222的次幂，不是最大周期的情况也能包括在内。后面的111表示不能全是i−1i-1i−1，否则最高层就不是iii了。

暴力做是O(nlogn)O(nlogn)O(nlogn)的，要考虑优化。

将gcd(i,n)gcd(i,n)gcd(i,n)相等的一起处理，对于1≤x<n1\le x<n1≤x<n，gcd(i,n)=x(1≤i<n)gcd(i,n)=x(1\le i<n)gcd(i,n)=x(1≤i<n)的iii的数量为φ(n/i)φ(n/i)φ(n/i)，显然。所以答案就是(∑x∣nn−12x⋅φ(n/x))−(n−2)\left(\sum_{x|n}^{n-1}2^x\cdot φ(n/x)\right)-(n-2)⎝⎛x∣n∑n−12x⋅φ(n/x)⎠⎞−(n−2)

那么搜索出所有的因数，搜索过程中可以算出φ(n/x)φ(n/x)φ(n/x)，最后时间复杂度为O(n⋅logn)O(\sqrt n\cdot logn)O(n⋅logn)。logloglog是快速幂。

CODE

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int mod = 1000000007;

LL p[20], k[20], ans, a[20][40], n;

//p[i]表示第i个质因数,k[i]表示p[i]的幂

//a[i][j] = p[i]^j

int cnt;

inline LL qpow(LL a, LL b) {

    LL re=1;

    for(;b;b>>=1,a=a*a%mod)if(b&1)re=re*a%mod;

    return re;

}

void dfs(int i, LL x, LL phi) {

    if(i > cnt) {

        if(x < n)

            ans = (ans + 1ll * qpow(2, x) * phi % mod) % mod;

        return;

    }

    for(int j = 0; j <= k[i]; ++j)

        dfs(i+1, x*a[i][j], phi/a[i][j]/(j<k[i]?p[i]:1)*(j<k[i]?p[i]-1:1)); //计算phi(n/x)

}

int main () {

    scanf("%lld", &n); LL N = n;

    for(LL i = 2; i*i <= n; ++i)

        if(n % i == 0) {

            p[++cnt] = i;

            a[cnt][0] = 1;

            while(n % i == 0) {

                n /= i, ++k[cnt];

                a[cnt][k[cnt]] = a[cnt][k[cnt]-1] * i;

            }

        }

    if(n > 1) p[++cnt] = n, k[cnt] = 1, a[cnt][0] = 1, a[cnt][1] = n;

    n = N;

    dfs(1, 1, n);

    printf("%lld\n", ((ans - n + 2) % mod + mod) % mod); //记得加mod

}

事实上官方题解是这样子的 Here

巴特西

Luogu P4270 [USACO18FEB]Cow Gymnasts (打表找规律)

题意

题解

CODE

最新文章

热门文章