Description
-
给定整数 n n n，求
[ ∑ i = 1 n ∑ j = 1 n d ( i j ) ] m o d ( 1 0 9 + 7 ) \left[\sum_{i = 1}^n \sum_{j = 1}^n d(ij)\right] \bmod (10^9 + 7) [i=1∑nj=1∑nd(ij)]mod(109+7) -
对于 100 % 100\% 100% 的数据 n ≤ 1 0 9 n\le 10^9 n≤109。
Solution
∑ i = 1 n ∑ j = 1 n d ( i j ) = ∑ i = 1 n ∑ j = 1 n ∑ x ∣ i ∑ y ∣ j [ gcd ( x , y ) = 1 ] = ∑ x = 1 n ∑ y = 1 n [ gcd ( x , y ) = 1 ] ∑ i = 1 n [ x ∣ i ] ∑ j = 1 n [ y ∣ j ] = ∑ x = 1 n ∑ y = 1 n [ gcd ( x , y ) = 1 ] ⌊ n x ⌋ ⌊ n y ⌋ = ∑ d = 1 n μ ( d ) ∑ x = 1 n [ d ∣ x ] ⌊ n x ⌋ ∑ y = 1 n [ d ∣ y ] ⌊ n y ⌋ = ∑ d = 1 n μ ( d ) ( ∑ i = 1 ⌊ n d ⌋ ⌊ n d i ⌋ ) 2 ( 1 ) = ∑ d = 1 n μ ( d ) ( ∑ i = 1 ⌊ n d ⌋ d ( i ) ) 2 ( 2 ) \begin{aligned} \sum_{i = 1}^n \sum_{j = 1}^n d(ij) & = \sum_{i = 1}^n \sum_{j = 1}^n \sum_{x\mid i} \sum_{y\mid j} [\gcd(x, y) = 1] \\ & = \sum_{x = 1}^n \sum_{y = 1}^n [\gcd(x, y) = 1] \sum_{i = 1}^n [x\mid i] \sum_{j = 1}^n [y\mid j] \\ & = \sum_{x = 1}^n \sum_{y = 1}^n [\gcd(x, y) = 1] \left\lfloor\dfrac{n}{x}\right\rfloor \left\lfloor\dfrac{n}{y}\right\rfloor \\ & = \sum_{d = 1}^n \mu(d) \sum_{x = 1}^n [d\mid x] \left\lfloor\dfrac{n}{x}\right\rfloor \sum_{y = 1}^n [d\mid y] \left\lfloor\dfrac{n}{y}\right\rfloor \\ & = \sum_{d = 1}^n \mu(d) \left(\sum_{i = 1}^{\left\lfloor\frac{n}{d}\right\rfloor} \left\lfloor\dfrac{n}{di}\right\rfloor\right)^2 & (1)\\ & = \sum_{d = 1}^n \mu(d) \left(\sum_{i = 1}^{\left\lfloor\frac{n}{d}\right\rfloor} d(i)\right)^2 & (2) \end{aligned} i=1∑nj=1∑nd(ij)=i=1∑nj=1∑nx∣i∑y∣j∑[gcd(x,y)=1]=x=1∑ny=1∑n[gcd(x,y)=1]i=1∑n[x∣i]j=1∑n[y∣j]=x=1∑ny=1∑n[gcd(x,y)=1]⌊xn⌋⌊yn⌋=d=1∑nμ(d)x=1∑n[d∣x]⌊xn⌋y=1∑n[d∣y]⌊yn⌋=d=1∑nμ(d)⎝⎜⎛i=1∑⌊dn⌋⌊din⌋⎠⎟⎞2=d=1∑nμ(d)⎝⎜⎛i=1∑⌊dn⌋d(i)⎠⎟⎞2(1)(2)
( 1 ) (1) (1) 中有两层整除分块。
μ \mu μ 用杜教筛，阈值为 1 0 6 10^6 106。
预处理 d d d 的前缀和。
以 k k k 为阈值，当 ⌊ n d ⌋ ≤ k \left\lfloor\dfrac{n}{d}\right\rfloor \le k ⌊dn⌋≤k 时用 ( 2 ) (2) (2) 的公式，以预处理过的 d d d 的前缀和来计算；当 ⌊ n d ⌋ > k \left\lfloor\dfrac{n}{d}\right\rfloor > k ⌊dn⌋>k 时用 ( 1 ) (1) (1) 中的整除分块计算。
那么预处理是 O ( k ) \Omicron(k) O(k) 的。
第一层整除分块中，若 ⌊ n d ⌋ ≤ k \left\lfloor\dfrac{n}{d}\right\rfloor \le k ⌊dn⌋≤k，即 d ≥ ⌊ n k ⌋ d \ge \left\lfloor\dfrac{n}{k}\right\rfloor d≥⌊kn⌋，那么就会用 d d d 的前缀和 O ( 1 ) \Omicron(1) O(1) 计算，这一段是 O ( n − n k ) ≤ O ( n ) \Omicron\left(\sqrt{n - \dfrac{n}{k}}\right) \le \Omicron(\sqrt{n}) O(n−kn )≤O(n ) 的。
第一层整除分块中，若
⌊
n
d
⌋
>
k
\left\lfloor\dfrac{n}{d}\right\rfloor > k
⌊dn⌋>k，即
d
<
⌊
n
k
⌋
d < \left\lfloor\dfrac{n}{k}\right\rfloor
d<⌊kn⌋，那么就会用整除分块来计算，一共是
∑
d
=
1
⌊
n
k
⌋
⌊
n
d
⌋
\sum_{d = 1}^{\left\lfloor\frac{n}{k}\right\rfloor} \sqrt{\left\lfloor\dfrac{n}{d}\right\rfloor}
∑d=1⌊kn⌋⌊dn⌋
，即
∫
0
n
k
n
x
d
x
=
2
n
k
\int_{0}^{\frac{n}{k}} \sqrt{\dfrac{n}{x}}\, dx = \dfrac{2n}{\sqrt{k}}
∫0knxn
dx=k
2n
也就是
O
(
n
k
)
\Omicron\left(\dfrac{n}{\sqrt{k}}\right)
O(k
n) 的。
综上，总时间复杂度为 O ( k + n + n k ) \Omicron\left(k + \sqrt{n} + \dfrac{n}{\sqrt{k}} \right) O(k+n +k n)， k k k 大约取 n 2 3 n^{\frac{2}{3}} n32 时最优，和杜教筛一样。
Code
// 18 = 9 + 9 = 18.
#include <iostream>
#include <cstdio>
#include <unordered_map>x
#define Debug(x) cout << #x << "=" << x << endl
typedef long long ll;
using namespace std;
const int MAXN = 1e6 + 5;
const int N = 1e6;
const int MOD = 1e9 + 7;
int p[MAXN], mu[MAXN], sum_mu[MAXN], d[MAXN], sum_d[MAXN], num[MAXN];
bool vis[MAXN];
void pre()
{
mu[1] = sum_mu[1] = d[1] = sum_d[1] = 1;
for (int i = 2; i <= N; i++)
{
if (!vis[i])
{
p[++p[0]] = i;
mu[i] = -1;
d[i] = 2;
num[i] = 1;
}
for (int j = 1; j <= p[0] && i * p[j] <= N; j++)
{
vis[i * p[j]] = true;
if (i % p[j] == 0)
{
mu[i * p[j]] = 0;
d[i * p[j]] = d[i] / (num[i] + 1) * (num[i] + 2);
num[i * p[j]] = num[i] + 1;
break;
}
mu[i * p[j]] = mu[i] * mu[p[j]];
d[i * p[j]] = d[i] * d[p[j]];
num[i * p[j]] = 1;
}
sum_mu[i] = sum_mu[i - 1] + mu[i];
sum_d[i] = (sum_d[i - 1] + d[i]) % MOD;
}
}
unordered_map<int, int> dp_mu;
int sublinear_mu(int n)
{
if (n <= N)
{
return sum_mu[n];
}
if (dp_mu.find(n) != dp_mu.end())
{
return dp_mu[n];
}
int res = 1;
for (int l = 2, r; l <= n; l = r + 1)
{
int k = n / l;
r = n / k;
res = (res - (ll)(r - l + 1) * sublinear_mu(k) % MOD + MOD) % MOD;
}
return dp_mu[n] = res;
}
int getsum_mu(int l, int r)
{
return (sublinear_mu(r) - sublinear_mu(l - 1) + MOD) % MOD;
}
int getsum_d(int n)
{
if (n <= N)
{
return sum_d[n];
}
int res = 0;
for (int l = 1, r; l <= n; l = r + 1)
{
int k = n / l;
r = n / k;
res = (res + (ll)(r - l + 1) * k % MOD) % MOD;
}
return res;
}
int block(int n)
{
int res = 0;
for (int l = 1, r; l <= n; l = r + 1)
{
int k = n / l;
r = n / k;
int tmp = getsum_d(k);
res = (res + (ll)getsum_mu(l, r) * tmp % MOD * tmp % MOD) % MOD;
}
return res;
}
int main()
{
pre();
int n;
scanf("%d", &n);
printf("%d\n", block(n));
return 0;
}