Description
给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.
Input
一个整数N
Output
如题
Sample Input
4
Sample Output
4
题解
$$ \sum_{d}{\sum_{i=1}^{n}{\sum_{j=1}^{n}[gcd(i,j)=d]}} $$
$$ = \sum_{d}{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}{\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}{[gcd(i,j)=1]}}} $$
$$ = \sum_{T}{\lfloor\frac{n}{T}\rfloor \lfloor\frac{n}{T}\rfloor\sum_{d|T}{\mu(\frac{n}{T})}} $$
令 $f[i]=\sum_{d|T}^{} \mu(\frac{T}{d})$
然后线性筛
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 10000000;
int mu[N + 5], prime[N + 5], g[N + 5];
long long sum[N + 5], cnt;
bool isnprime[N + 5];
void get_g()
{
mu[1] = 1;
for (int i = 2; i <= N; i++)
{
if (!isnprime[i])
{
prime[++cnt] = i;
mu[i] = -1;
g[i] = 1;
}
for (int j = 1; j <= cnt && i * prime[j] <= N; j++)
{
isnprime[i * prime[j]] = 1;
if (i % prime[j])
mu[i * prime[j]] = -mu[i], g[i * prime[j]] = mu[i] - g[i];
else
{
mu[i * prime[j]] = 0;
g[i * prime[j]] = mu[i];
break;
}
}
}
for (int i = 1; i <= N; i++)
{
sum[i] = sum[i - 1] + g[i];
}
}
int main()
{
get_g();
int n;
scanf("%d", &n);
long long ans = 0, last;
for (int i = 1; i <= n; i = last + 1)
{
last = n / (n / i);
ans += (long long)(sum[last] - sum[i - 1]) * (n / i) * (n / i);
}
printf("%lld\n", ans);
}