BZOJ-2818 Gcd

链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2818

$Time\;Limit:\;10\;Sec$

$Memory\;Limit:\;256\;MB$

Description

给定整数N，求$1 \le x,y\le N$且$Gcd(x,y)$为素数的数对$(x,y)$有多少对.

Input

一个整数$N$

Output

如题

Sample Input

$4$

Sample Output

$4$

HINT

$hint$

对于样例$(2,2),(2,4),(3,3),(4,2)$

$1\le N\le 10^7$

题解

\[设sum[i]=\sum_{n=1}^{i}\varphi[n]\\\] \[\begin{split} &\sum_{i=1}^{N}\sum_{j=1}^{N}[gcd(i,j)=p]\\ =&\sum_{i=1}^{N}\sum_{j=1}^{N}\left [ gcd\left ( \frac{i}{p},\frac{j}{p} \right )= 1 \right ]\\ =&\sum_{i=1}^{nump}(2\times sum[\frac{N}{prime[i]}]-1)\\ \end{split}\]

值得注意的是对于每一组$i,j$，都将$(1,1)$重复计算，所以统计时应当减去多算的部分

//Time: 1200ms Memory:196600kB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7 + 5;
int m[N], phi[N], p[N], nump, n;
ll ans, sum[N];
void make()	
{
	phi[1] = 1;
	for(int i = 2; i <= n; ++i)
	{
		if(!m[i])
		{
			p[++nump] = i;
			phi[i] = i - 1;
		}
		for(int j = 1; j <= nump && p[j] * i <= n; ++j)
		{
			m[p[j] * i] = 1;
			if (i % p[j] == 0)
			{
				phi[p[j] * i] = phi[i] * p[j];
				break;
			}
			else phi[p[j] * i] = phi[i] * (p[j] - 1);
		}
	}
}
int main()
{
	cin >> n;
	make(); 
	for(int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + phi[i];
	for(int i = 1; i <= nump; ++i) ans += sum[n / p[i]] * 2 - 1;
	cout << ans << endl;
	return 0;
}

Tags:

0 comments