2018ICPC南京賽區網絡賽J Sum（素數篩+找規律）

素數篩鏈接：https://blog.csdn.net/dl962454/article/details/76595623

【題意】

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 <iostream>
#include <cstring>
#include <cstdio>using namespace std;const int maxn=2e7+10;//1int prime[maxn];
int vis[maxn];
long long f[maxn],ans[maxn];void isprime()
{int idx=0;f[1]=1;memset(vis,0,sizeof(vis));for(int i=2;i<maxn;i++){if(!vis[i]){prime[idx++]=i;f[i]=2;}for(int j=0;j<idx&&prime[j]*i<maxn;j++){vis[i*prime[j]]=1;if(i%prime[j]==0){if(i%(prime[j]*prime[j])==0){f[i*prime[j]]=0;}else f[i*prime[j]]=f[i]/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()
{ios::sync_with_stdio(false);cin.tie(0);int T,n;isprime();scanf("%d",&T);while(T--){scanf("%d",&n);printf("%lld\n",ans[n]);}return 0;
}

?