51nod 欢乐手速场C 开心的小Q

开心的小Q

tangjz (命题人)quailty (测试)

基准时间限制：1 秒 空间限制：131072 KB 分值: 80

如果一个数字存在一个约数是完全平方数，那么小Q就认为这个数是有趣的。

小Q喜欢收集有趣的数字，每找到一个有趣的数，小Q就会变得很开心。

小Q发现12是有趣的，18也是有趣的，它们都是36的约数，而在36的约数中，还有3个数是有趣的，它们是4、9、36。

小Q很好奇，在a~b里每个数字各有多少个有趣的约数，由于a和b太大了，所以他只想知道这些个数之和是多少。

例如4有1个有趣的约数，8有2个有趣的约数，9有1个有趣的约数，所以1~10里每个数的有趣约数个数之和是4。

Input

输入数据包括2个数：a, b，中间用空格分隔。（1≤a≤b≤10^9）

Output

输出a~b里每个数字的有趣约数个数之和。

Input示例

1 10

Output示例

4

题解：一拿到题目我是一脸懵比的，然后推着推出个答案是∑ni=1∑d|i(1−|μ(d)|)

设f(n)表示1-n中有平方因子的个数，f(n)=Σ(i,1,n)（1-|μ(i)|)根据容斥原理可以化简成

n-Σ(i,1,sqrt(n))μ[i]*trunc(n/i/i)；

那么答案就可以表示为f(n/i)（i=1…n）

用分块计算就可以了。

code:

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long ll;
const int N=+;
int n,m;
int mu[N],a[N];
bool bz[N];
inline ll f(int x)
{
    ll ans=x;
    int t=trunc(sqrt(x));
    fo(i,,t)
    ans-=mu[i]*l*(x/i/i);
    return ans;
}
ll calc(int x)
{
    int t=;
    ll ans=;
    while (t<x)
    {
        int t1=max(t+,x/(x/t-));
        ans+=f(t)*l*(x/t-x/t1);
        t=t1;
    }
    ans+=f(x);
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    mu[]=;
    int tot=,lim=;
    fo(i,,lim)
    {
        if (!bz[i])
        {
            a[++tot]=i;
            mu[i]=-;
        }
        fo(j,,tot)
        {
            if (i*a[j]>lim)break;
            bz[i*a[j]]=;
            if (i%a[j]==)
            {
                mu[a[j]*i]=;
                break;
            }
            mu[i*a[j]]=-mu[i];
        }
    }

    printf("%lld\n",calc(m)-calc(n-));
    return ;
}