ACM-ICPC 2018 南京赛区网络预赛 J. Sum 【筛法】

题目大意： f(n) 表示 n =a*b （a,b 都为非 平方倍数） ，a,b不同时的对数
计算 f(1)+f(2)+…+f(n)

题目分析：我们分析一下在和当中每个数的贡献度
举例 当 n = 8时
因子=1时的 贡献度 有 1*1 (1*2 ,1*3, 1*5,1*6，1*7 ) 后面这一部分要*2 1+5*2=11
因子=2时的贡献度 有 2*2 (2*3) （因为2*1可以在之前算到，所以我们再后面计算的时候只从比当前的数大的对数）1+1*2=3
>=3 $>=3$时 就没有贡献
所以总的贡献就是3+11=14
总的来说，我们只要算出到n为止有多少个满足条件的a,b，那么对于每一个非平方数倍数因子i ,他的贡献度就是 (cnt[n/i]-cnt[i])*2+1
那么我们只要预处理用筛法筛去平方数和他们的倍数即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e7+50;
ll vis[maxn+5];
ll cnt[maxn+5];
void init()
{
    for(int i=0; i<=maxn; i++) vis[i]=1;
    for(int i=2; i*i<=maxn; i++)
    {
        int k=i*i;
        if(!vis[k])continue;
        for(int j=k; j<=maxn; j+=k)
        {
            vis[j]=0;
        }
    }
    for(int i=1; i<=maxn; i++)
    {
        cnt[i]=cnt[i-1]+vis[i];
    }
}
int main()
{
    init();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        ll ans=0;
        scanf("%d",&n);
        for(int i=1; i*i<=n; i++)
        {
            if(!vis[i])continue;
            ans+=((cnt[n/i]-cnt[i])*2+1);
            //cout<<ans<<endl;
        }
        printf("%lld\n",ans);

    }
    return 0;
}