前面的几个性质的思路参考自这篇Blog，主要是对一些我觉得难以理解的地方重写一下，以及对最后结论及实现进行更详细的证明。

题面

$n$ $[1, n]$ $i$ $i - 1$ 个平台并落下，求有多少种排列能使无论多少次操作每个平台的奶牛数都不改变。

$1 \le n \le 10^{12}$ 。

$(1, 1, 1, 1), (2, 2, 2, 2), (3, 3, 3, 3), (4, 4, 4, 4), (2, 3, 2, 3), (3, 2, 3, 2)$ 。

Solution

一道纯粹的人类智慧题。。。

$i$ $\xi$ $i$ $\xi$ 层所需要的旋转次数。也就是对于一个合法的排列，两个同一高度平台之间的距离即为平台内所有牛的循环周期。

首先对于符合条件的排列，有好几个奇怪的性质：

$i$ $i$ 层的奶牛平移过来，而不可以是从更高层的奶牛掉下来。

$m$ $m - 1$ $m$ $m + 1$ $m - 1$ $2$ $3$ $\cdots$ $m - 1$ $m$ $m - 1$ $m - 1$ $m$ ，然后以此类推即可证明所有层数都是由对应层数平移过来的，得证。

$i$ $i$ 的约数。

$i$ $T_i$ $k$ $i = kT_i$ ，得证。

$i - 1$ $i$ 层奶牛循环周期的约数。

$i$ $i$ $i$ $i - 1$ $i$ $T_{i - 1} \mid T_i$ ，得证。

$1$ 。

$T_i \mid i, T_{i + 1} \mid i + 1$ $T_{i} \mid T_{i + 1}$ $\gcd(i, i + 1) = 1$ $\gcd(T_i, T_{i + 1}) = 1$ $1$ $T_1 = T_2 = \cdots = T_{n - 1} = 1$ $i$ $i - 1$ $1$ $i - 1$ $1$ .

以此我们便可以得出结论：

a n s = 2 - n + \sum_{i = 1}^{n - 1} 2^{gcd (n, i)}

$i$ $i$ $i$ $n$ $n$ 最大的 $\gcd(n, i)$ $n = 6, i = 3, \gcd = 3$ 的例子：

Oops! The image is blocked! Please visit my own website to observe the image! 图片被墙了，请通过文章头的跳转链接访问！

$2^{\gcd(n, i)}$ $A, B, C$ $i$ $i$ $i$ $-1$ 。

$i$ $A = i$ $B$ $i$ $B$ $i + 1$ $i - 1$ $i$ $i + 1$ $C$ $i$ $i + 1$ $i + 2$ $C$ $A$ $i + 2$ $i$ $1$ $i + 2 = 5$ $3 \nmid 5$ $i + 1$ $i$ 要么不是，不是的时候数也唯一确定，故可以如此枚举。

$i$ $i + 1$ 。

$i$ $i + 1$ $1$ $i - 1$ $i + 2$ $T_{i + 1} \ge 2$ $i + 2$ $i + 1$ $T_{i + 1} = 1$ $i$ $i + 1$ $i + 1$ $1$ 的条件的，所以这样才是合法的。故得证。

$i$ $i + 1$ $i + 1$ $2^{\gcd(n, i)} - 1$ $i = n$ $i + 1$ $n$ $n$ $n$ 则为唯一的方案，如此最终答案便为：

\begin{aligned} a n s & = \sum_{i = 1}^{n - 1} (2^{gcd (n, i)} - 1) + 1 \\ = 2 - n + \sum_{i = 1}^{n - 1} 2^{gcd (n, i)} \\ = 2 - n - 2^{n} + \sum_{i = 1}^{n} 2^{gcd (n, i)} \end{aligned}

然后发现数据范围这个柿子肯定过不去，于是考虑优化，继续推柿子：

\begin{aligned} \sum_{i = 1}^{n} 2^{gcd (n, i)} & = \sum_{j = 1}^{n} 2^{j} \sum_{i = 1}^{n} [gcd (n, i) = j] \\ = \sum_{j = 1}^{n} 2^{j} \sum_{i = 1}^{n} [j ∣ i \land j ∣ n \land gcd (\frac{n}{j}, \frac{i}{j}) = 1] \\ = \sum_{j = 1}^{n} (2^{j} \times φ (\frac{n}{j}) \times [j ∣ n]) \\ = \sum_{j ∣ n} (2^{j} \times φ (\frac{n}{j})) \\ = \sum_{j ∣ n} (2^{\frac{n}{j}} \times φ (j)) \end{aligned}

$O(\sqrt{n}\log n)$ $O(\sqrt{n})$ $O(\sqrt{n})$ $O(n)$ $O(n^{\frac{2}{3}})$ 实现，刚好能过，不过 duck 不必。

$p_i$ $c_i \neq 0$ ，如果有：

n = \prod_{i = 1}^{k} p_{i}^{c^{i}}

那么：

φ (n) = n \times \prod_{i = 1}^{k} \frac{p_{i} - 1}{p_{i}}

$n$ $O(1)$ $O(\sqrt{n})$ $\log$ $2^j$ long long $n \div \prod p_i$ $\prod p_i - 1$ ，否则会爆 long long，当然像我一样直接用 __int128_t 可以直接忽略这些问题。

至此此题解决，还是很精妙的。

Code


86
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
#define MOD (ll)(1e9 + 7)
24

25
template< typename T = int >
26
inline T read(void);
27

28
ll N;
29
int tot(0);
30
pair < ll, int > fact[1100000];
31
int cur[1100000];
32
__int128_t ans(0);
33

34
__int128_t qpow(ll a, ll b){
35
    __int128_t ret(1), mul(a);
36
    while(b){
37
        if(b & 1)ret = ret * mul % MOD;
38
        b >>= 1;
39
        mul = mul * mul % MOD;
40
    }return ret;
41
}
42

43
void dfs(int p = 1, ll base = 1, __int128_t phi = 1, __int128_t div = 1){
44
    if(p > tot){
45
        phi *= base, phi /= div, phi %= MOD;
46
        ans = (ans + phi * qpow(2, N / base) % MOD) % MOD;
47
        return;
48
    }
49
    dfs(p + 1, base, phi, div);
50
    phi *= fact[p].first - 1;
51
    div *= fact[p].first;
52
    for(int i = 1; i <= fact[p].second; ++i)
53
        base *= fact[p].first, dfs(p + 1, base, phi, div);
54
}
55

56
int main(){
57
    N = read < ll >();
58
    ll tmp(N); ll cur(2), cnt(0);
59
    while(tmp > 1){
60
        if(cur * cur > tmp)break;
61
        while(tmp % cur == 0)tmp /= cur, ++cnt;
62
        if(cnt)fact[++tot] = {cur, cnt}, cnt = 0;
63
        ++cur;
64
    }if(tmp > 1)fact[++tot] = {tmp, 1};
65
    dfs();
66
    ans = ((((ans + 2 - N) % MOD) - qpow(2, N)) % MOD + MOD) % MOD;
67
    printf("%lld\n", (ll)ans);
68
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
69
    return 0;
70
}
71

72
template < typename T >
73
inline T read(void){
74
    T ret(0);
75
    short flag(1);
76
    char c = getchar();
77
    while(c != '-' && !isdigit(c))c = getchar();
78
    if(c == '-')flag = -1, c = getchar();
79
    while(isdigit(c)){
80
        ret *= 10;
81
        ret += int(c - '0');
82
        c = getchar();
83
    }
84
    ret *= flag;
85
    return ret;
86
}

UPD

update-2022_11_09 初稿

LG-P4270 [USACO18FEB]Cow Gymnasts P Solution

更好的阅读体验戳此进入

题面

Solution

Code

UPD