题面

设d(x)d(x)d(x)为xxx的约数个数，给定NNN，求 ∑i=1N∑j=1Nd(ij)\sum^{N}_{i=1}\sum^{N}_{j=1} d(ij)i=1∑Nj=1∑Nd(ij)

N<=109N<=10^9N<=109

题目分析

有这样一个结论

d(ij)=∑x∣i∑y∣j[(x,y)==1]d(ij)=\sum_{x|i}\sum_{y|j}[(x,y)==1]d(ij)=x∣i∑y∣j∑[(x,y)==1]这道题就是下面这道题的数据增强版,那么这个结论的证明就不再赘述,请自行查看下面的(蒟蒻)博客传送门:[SDOI2015][bzoj 3994][Luogu P3327] 约数个数和

Ans=∑k=1Nμ(k)(∑x=1⌊Nk⌋⌊Nkx⌋)2\large Ans=\sum_{k=1}^N\mu(k)\left(\sum_{x=1}^{⌊\frac{N}{k}⌋}⌊\frac{N}{kx}⌋\right)^2Ans=k=1∑Nμ(k)⎝⎜⎛x=1∑⌊kN⌋⌊kxN⌋⎠⎟⎞2

由于数据范围的增强,我们不能预处理完整个10910^9109,于是就外层整除分块优化

内层杜教筛来算μ\muμ的前缀和,时间复杂度为Θ(N23)\Theta (N^{\frac 23})Θ(N32)
后面平方的底数实际上等于[1,⌊Nk⌋]\left[1,⌊\frac{N}{k}⌋\right][1,⌊kN⌋]的约数个数和的前缀和,可以直接Θ(⌊Nk⌋)\Theta(\sqrt {⌊\frac{N}{k}⌋})Θ(⌊kN⌋)算,预处理出前N23N^{\frac23}N32的约数个数和的前缀和后,总时间复杂度就如杜教筛一样为Θ(N23)\Theta(N^\frac 23)Θ(N32)

总时间复杂度为Θ(N23)\Theta (N^{\frac 23})Θ(N32)

AC code

#include <cstdio>

#include <algorithm>

#include <map>

using namespace std;

typedef long long LL;

const int N = 1e6 + 1;

const int mod = 1e9 + 7;

int Cnt, Prime[N], mu[N], d[N], a[N]; //a[i]存的是i的最小质因数的次数+1

bool IsnotPrime[N];

void init()

{

	mu[1] = d[1] = a[1] = 1;

	for(int i = 2; i < N; ++i)

	{

		if(!IsnotPrime[i])

			Prime[++Cnt] = i, mu[i] = -1, a[i] = d[i] = 2;

		for(int j = 1; j <= Cnt && i * Prime[j] < N; ++j)

		{

			IsnotPrime[i * Prime[j]] = 1;

			if(i % Prime[j] == 0)

			{

				mu[i * Prime[j]] = 0;

				d[i * Prime[j]] = d[i] / a[i] * (a[i * Prime[j]] = a[i] + 1);

				break;

			}

			mu[i * Prime[j]] = -mu[i];

			d[i * Prime[j]] = d[i] * (a[i * Prime[j]] = 2);

		}

	}

	for(int i = 1; i < N; ++i)

		(d[i] += d[i-1]) %= mod, (mu[i] += mu[i-1]) %= mod;

}

inline int sum_d(int n) //约数个数和的前缀和,也就是后面个平方的底数

{

	if(n < N) return d[n];

	int ret = 0;

	for(int i = 1, j; i <= n; i=j+1)

	{

		j = n/(n/i);

		ret = (ret + (LL)(n/i) * (j-i+1) % mod) % mod;

	}

	return ret;

}

map<int, int>s;

inline int sum_mu(int n)

{

	if(n < N) return mu[n];

	if(s.count(n)) return s[n];

	int ret = 1;

	for(int i = 2, j; i <= n; i=j+1)

	{

		j = n/(n/i);

		ret = (ret - (LL)sum_mu(n/i)*(j-i+1)%mod) % mod;

	}

	return s[n]=ret;

}

int solve(int n)

{

	int ret = 0, last = 0, tmp, tmp2;

	for(int i = 1, j; i <= n; i=j+1)

	{

		j = n/(n/i);

		tmp = sum_mu(j), tmp2 = sum_d(n/i), tmp2 = (LL)tmp2 * tmp2 % mod;

		//tmp2存后面那个平方的值

		ret = (ret + (LL)((tmp-last) % mod) * tmp2 % mod) % mod;

		last = tmp;//这利用了一个小优化,本来是sum_mu(j)-sum_mu(i-1),

				   //我们把sum_mu(i-1)的值存下来,就少计算一次,last存上一次答案

				   //然而我后来看发现这优化并没有什么卵用,本来就记忆化了...

	}

	return ret;

}

int main ()

{

	init(); int n;

	scanf("%d", &n);

	printf("%d\n", (solve(n)+mod)%mod);

}

.

.

.

少有的一A

二刷:bzoj rank 7

CODE

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1000005;

const int mod = 1e9 + 7;

int prime[MAXN/10], cnt, mu[MAXN], d[MAXN], a[MAXN];

bool vis[MAXN];

inline void Pre_Work(int n) {

	mu[1] = d[1] = a[1] = 1;

	for(int i = 2; i <= n; ++i) {

		if(!vis[i])

			prime[++cnt] = i, mu[i] = -1, d[i] = a[i] = 2;

		for(int j = 1; j <= cnt && i*prime[j] <= n; ++j) {

			vis[i*prime[j]] = 1;

			if(i % prime[j] == 0) {

				mu[i*prime[j]] = 0;

				d[i*prime[j]] = d[i] / a[i] * (a[i*prime[j]] = a[i]+1);

				break;

			}

			mu[i*prime[j]] = -mu[i];

			d[i*prime[j]] = d[i] * (a[i*prime[j]] = 2);

		}

	}

	for(int i = 2; i <= n; ++i)

		mu[i] += mu[i-1], (d[i] += d[i-1]) %= mod;

}

map<int, int>MU;

inline int sum_mu(int n) {

	if(n < MAXN) return mu[n];

	if(MU.count(n)) return MU[n];

	int re = 1;

	for(int i = 2, j; i <= n; i = j+1) {

		j = n/(n/i);

		re = (re - 1ll * (j-i+1) * sum_mu(n/i) % mod) % mod;

	}

	return MU[n]=re;

}

map<int, int>D;

inline int sum_d(int n) {

	if(n < MAXN) return d[n];

	if(D.count(n)) return D[n];

	int re = 0;

	for(int i = 1, j; i <= n; i = j+1) {

		j = n/(n/i);

		re = (re + 1ll * (j-i+1) * (n/i) % mod) % mod;

	}

	return D[n]=re;

}

inline int sqr(int x) { return 1ll*x*x%mod; }

inline int solve(int n) {

	int re = 0;

	for(int i = 1, j; i <= n; i = j+1) {

		j = n/(n/i);

		re = (re + 1ll * (sum_mu(j)-sum_mu(i-1)) % mod * sqr(sum_d(n/i)) % mod) % mod;

	}

	return re;

}

int main() {

	int n;

	scanf("%d", &n);

	Pre_Work(min(n, MAXN-1));

	printf("%d\n", (solve(n) + mod) % mod);

}

巴特西

[bzoj 4176] Lucas的数论 (杜教筛 + 莫比乌斯反演)

题面

题目分析

AC code

CODE

最新文章

热门文章