怎么做网站优化,app大全视频app大全,扬州建设集团招聘信息网站,无锡百姓网推广素数筛链接#xff1a;https://blog.csdn.net/dl962454/article/details/76595623 【题意】 f(i)#xff1a;能拆成两个数的乘积#xff0c;并且这两个数要求没有平方因子#xff0c;并且两个数的位置互换算两种方案。 最后求f(1)f(2)f(3)...f(n#xff09;。 【解题思路】…素数筛链接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个。 那么最后总结起来再用个欧拉筛就是这样的。 对于素数df(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 cstdiousing namespace std;const int maxn2e710;//1int prime[maxn];
int vis[maxn];
long long f[maxn],ans[maxn];void isprime()
{int idx0;f[1]1;memset(vis,0,sizeof(vis));for(int i2;imaxn;i){if(!vis[i]){prime[idx]i;f[i]2;}for(int j0;jidxprime[j]*imaxn;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 i1;imaxn;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;
} 转载于:https://www.cnblogs.com/Fy1999/p/9601175.html
