P4270 [USACO18FEB] Cow Gymnasts P

题目描述

给定正整数 $n$，求有多少个整数数列 $\{a_n\}$ 满足以下条件：

$$\forall i \in [0, n), a_i = \displaystyle\sum_{j=1}^n[a_{(i-j+1)\bmod n} \geq j]$$

这里 $1\leq n\leq 10^{12}$。

解法说明

考虑固定 $m=\min_{i=0}^{n-1}\{a_i\}$。
对某个 $a_i=m$，我们有 $\forall j \in [1, m], a_{(i-j+1)\bmod n} \geq m \geq j$，因此 $\forall j \in (m, n), a_{(i-j+1)\bmod n} < j$，若取 $j=m+1$ 即有 $m \leq a_{(i-j+1)\bmod n} < j$，相当于 $a_{(i-j+1)\bmod n} = m$。
此外，记 $M=\min_{i=0}^{n-1}\{a_i\}$，我们有 $M \leq m + 1$，这是因为对某个 $a_i=M$，$\forall j \in (M, n), a_{(i-j+1)\bmod n} \leq M < j$，同理有 $\forall j \in [1, M], a_{(i-j+1)\bmod n} \geq j$，换言之 $\forall j \in (m, M], a_{(i-j+1)\bmod n} \geq j > m$，这说明 $M \leq m + 1$。

综上所述，所求为 $1+\displaystyle\sum_{i=1}^n(2^{\gcd(i, n)}-1)$。

$$\begin{aligned} 1+\displaystyle\sum_{i=1}^{n-1}(2^{\gcd(i, n)}-1) &= -n+2+\sum_{i=1}^{n-1} 2^{\gcd(i, n)} \\ &= -n+2+\sum_{d\mid n\land d\neq n} 2^d\varphi\left(\dfrac{n}{d}\right) \end{aligned}$$

暴力计算即可达到 $\Theta(\sqrt{n}+\tau(n)\log{p}+\displaystyle\sum_{d\mid n}\dfrac{1}{\sqrt{d}})=\Theta(\tau(n)\log{p}+\sqrt{n}\log\log{n})$，可以通过本题。

代码实现

#include <algorithm>
#include <cstdio>

using ll = long long;

constexpr int Mod = 1e9 + 7;

ll powmod(ll t, ll p) {
  p %= (Mod - 1);
  ll r = 1;
  while (p) {
    if (p & 1) r = r * t % Mod;
    t = t * t % Mod;
    p >>= 1;
  }
  return r;
}

ll phi(ll n) {
  ll res = n;
  for (ll d = 2; d <= n / d; ++d)
    if (n % d == 0) {
      res = res / d * (d - 1);
      while (n % d == 0) n /= d;
    }
  if (n > 1) res = res / n * (n - 1);
  return res;
}

ll n, ans;

int main() {
  scanf("%lld", &n);
  ans = (Mod - n % Mod + 2) % Mod;
  auto add = [&](ll d) { ans = (ans + powmod(2, d) * phi(n / d)) % Mod; };
  for (ll d = 1; d <= n / d; ++d) {
    if (n % d) continue;
    add(d);
    if (n / d != d && n / d != n) add(n / d);
  }
  printf("%lld", ans);
}