【题解】BZOJ-4176 Lucas的数论

Lucas的数论

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∑n​j=1∑n​d(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∑n​j=1∑n​d(ij)​=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]⌊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}} ∫0kn​​xn​ ​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;
}
上一篇:变分自编码器(VAE)的理解与实现


下一篇:normal + lognormal