【计蒜客】2018ICPC南京赛区网络赛J Sum（素数筛+找规律）

题目链接

【题意】

f(i)：能拆成两个数的乘积，并且这两个数要求没有平方因子，并且两个数的位置互换算两种方案。

最后求f(1)+f(2)+f(3)+...f(n）。

 

【解题思路】

还是对欧拉筛的理解不够透彻，比赛的时候一直是筛完素数再去求解f(i)，其实是可以一边筛一边求解的。

不难发现，当i是素数时，f(i)=2，当i有3个及以上相同因子时，f(i)=0（比如2*2*2*3不可能组合成两个都没有平方因子的数），当i没有相同因子（假设因子数为n）时，f(i)=2^n（比如2*3*5是8个），当i有两个相同因子（假设有p对相同因子，n个不同因子）时，f(i)=2^n/2^p（比如2*2*3*3*5是2个）。

那么最后总结起来再用个欧拉筛就是这样的。

对于素数d：f(d)=2

当d|p时，若d|p^2，则f(d*p)=0，否则f(d*p)=f(d)/2

反之，则f(d*p)=2*f(d)

 

【代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=2e7+5;
int vis[maxn],prime[maxn];
LL f[maxn],ans[maxn];
void isprime()
{
    int cnt=0;
    f[1]=1;
    for(int i=2;i<maxn;i++)
    {
        if(!vis[i])
        {
            prime[cnt++]=i;
            f[i]=2;
        }
        for(int j=0;j<cnt&& i*prime[j]<maxn;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                if(i%(prime[j]*prime[j])==0)
                    f[i*prime[j]]=0;//一个数的相同因子有3个及以上
                else f[i*prime[j]]=f[i]/2;//一个数的相同因子有2个
                break;
            }
            else f[i*prime[j]]=f[i]*2;//没有相同因子
        }
    }
    for(int i=1;i<maxn;i++)
        ans[i]=ans[i-1]+f[i];
}
int main()
{
    isprime();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int x;
        scanf("%d",&x);
        printf("%lld\n",ans[x]);
    }
    return 0;
}