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 ;
}