[Ahoi2005]COMMON 约数研究【欧拉线性筛的应用】

2022-11-14 20:07:34

1968: [Ahoi2005]COMMON 约数研究

Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 2939 Solved: 2169
[Submit][Status][Discuss]

Description

Input

只有一行一个整数 N（0 < N < 1000000）。

Output

只有一行输出，为整数M，即f(1)到f(N)的累加和。

Sample Input

Sample Output

题解

我们知道一个数x的约数个数 = (a1 + 1) * (a2 + 1) * (a3 + 1)......(ak + 1)

其中x的质因子分解：x = p1^a1 * p2^a2 * p3^a3 ......pk^ak

现在我们需要算出所有数的约数个数和

直接算？O(n√n) n <= 1000000肯定超时

考虑线性筛

若i为质数，显然f[i] = 2

若i不为质数，它一定会在线性筛中被它除去最小的一个质因数后的那个数筛去

例如 20 = 2 * 2 * 5，那么在筛到10 = 2 * 5时，我们会用 2 * 10 筛去20

由于比10及10以前的f值已经确定

这个时候f[20] = f[10] + f[10 / 2^1] = (1 + 1) * (1 + 1) + (1 + 1) = 3 * 2

也就是f[i * prime[j]] = f[i] + f[i除去所有prime[j]后的数]

UPD2018.1.27:

其实这道题有更快的方法。。。。是我蠢了

∑[N/i]即可

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<bitset>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

using namespace std;

const int maxn = 1000005,maxm = 100005,INF = 1000000000;

int prime[maxn],primei = 0,n;

LL f[maxn],M = 0;

bitset<maxn> isp;

void cal(){

	int t;

	isp.set();

	f[1] = 1;

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

		if (isp[i]) prime[++primei] = i,f[i] = 2;

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

			isp[i * prime[j]] = false;

			for (t = i; t % prime[j] == 0; t /= prime[j]);

			f[i * prime[j]] = f[i] + f[t];

			if (i % prime[j] == 0) break;

		}

	}

	REP(i,n) M += f[i];

}

int main()

{

	cin >> n;

	cal();

	cout << M << endl;

	return 0;

}

UPD：

#include<iostream>

using namespace std;

int main(){

    int n,nxt; cin>>n;

    long long int ans = 0;

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

        nxt = n / (n / i);

        ans += (long long int)n / i * (nxt - i + 1);

    }

    cout<<ans<<endl;

    return 0;

}

码农公寓