ACM模版
描述
题解
51Nod
上这种类型的问题大概有个七八道吧，都是莫比乌斯函数 + 杜教筛，由于我的数论基础实在是差，学得始终不得章法，每次都得看大佬们的题解。
WorldWide_D’s blog 有详细的问题分析和推导过程，大家可以仔细看看，我就不说太多废话了。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN =
4e5 +
10;
int tot;
int pri[MAXN];
int miu[MAXN +
5];
ll l, r, ans;
bool bz[MAXN +
5];
void init()
{
miu[
1] =
1;
for (
int i =
2; i <= MAXN; i++)
{
if (!bz[i])
{
miu[i] = -
1;
pri[tot++] = i;
}
for (
int j =
0; j < tot; j++)
{
int tmp = i * pri[j];
if (tmp > MAXN)
{
break;
}
bz[tmp] =
1;
if (i % pri[j] ==
0)
{
miu[tmp] =
0;
break;
}
miu[tmp] = -miu[i];
}
}
}
ll calc(ll n)
{
if (!n)
{
return 0;
}
ans =
0;
for (
int k =
1; (ll)k * k <= n; k++)
{
if (miu[k] !=
0)
{
ll m = n / ((ll)k * k), s =
0;
for (
int i =
1; (ll)i * i * i <= m; i++)
{
for (
int j = i +
1; (ll)i * j * j <= m; j++)
{
s += (m / ((ll)i * j) - j) *
6 +
3;
}
s += (m / ((ll)i * i) - i) *
3 +
1;
}
if (miu[k] ==
1)
{
ans += s;
}
else
{
ans -= s;
}
}
}
return (ans + n) /
2;
}
int main()
{
init();
scanf(
"%lld%lld", &l, &r);
printf(
"%lld\n", calc(r) - calc(l -
1));
return 0;
}
