2019-01-04 09:51:39

#### $\sum\limits_{k=1}^{n}k*\sum\limits_{i=1}^{\lfloor n/k\rfloor}\sum\limits_{J=1}^{\lfloor m/k\rfloor}[gcd(i,j)=1]$

$gcd$ 改成 $\mu$：

#### $\sum\limits_{k=1}^{n}k*\sum\limits_{d=1}^{\lfloor n/k\rfloor}\lfloor \frac{n}{kd}\rfloor \lfloor \frac{m}{kd}\rfloor*\mu(d)$

#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 100005

using namespace std;

int n, m, mu[maxn], p[maxn], cnt;
long long ans = 0;
bool vis[maxn];

void Init()
{
vis[1] = 1, mu[1] = 1;
for (int i = 2; i < maxn; ++i)
{
if (!vis[i])
p[++cnt] = i, mu[i] = -1;
for (int j = 1; j <= cnt && p[j] * i < maxn; ++j)
{
int x = i * p[j];
vis[x] = 1, mu[x] = -mu[i];
if (i % p[j] == 0)
{
mu[x] = 0;
break;
}
}
}
}

int main()
{
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
Init();
if (n > m)
swap(n, m);
for (int k = 1; k <= n; ++k)
{
int lim = n / k, res = 0;
for (int d = 1; d <= lim; ++d)
res += (n / (k * d)) * (m / (k * d)) * mu[d];
ans += 1ll * res * k;
}
ans = ans * 2 - n * m;
printf("%lld\n", ans);
return 0;
}
• star
首页