题目链接 题意： 定义cnt[i]是任意一个数分解成无平方整数的方案数 给定n 求前n项cnt[i]的和 思路： 遇到这种题就多写几个数看看 找找规律 差不多就出来了 有那么几种情况 ①是质数：方案数铁定是1 ②不是质数：那么他的方案数是他两个因子方案数的乘积加上下面特殊考虑：
若该合数为平方数，则分解方法数要除4 若该合数的其中一个因子是n次方数（n≥3），则分解方法数为0既然用到判断是不是质数，且数据量是2e7 那么肯定用到线性筛，我们在线性筛的过程中直接处理出结果来 那么就需要对线性筛有一定理解
#include<iostream> #include<algorithm> #include<string.h> #include<map> #include<queue> #include<cmath> #include<cstdio> #define ll long long #define inf 0x3f3f3f3f using namespace std; const int maxn=2e7+5; bool p[maxn]; int prime[maxn],k=0; int cnt[maxn]; int sum[maxn]; void init(){ p[0]=p[1]=true; cnt[1]=1; sum[1]=1; for(int i=2;i<maxn;i++) { if(!p[i]) { cnt[i]=2; prime[k++]=i; } for(int j=0;j<k&&(ll)i*prime[j]<maxn;j++) { int temp=i*prime[j]; p[temp]=true; cnt[temp]=cnt[i]*cnt[prime[j]]; if(i%(prime[j]*prime[j])==0)//含x次方数的情况 cnt[temp]=0; if(i%prime[j]==0)//含平方数的情况 { cnt[temp]/=4; break; } } sum[i]=sum[i-1]+cnt[i]; } } int main() { int t; init(); scanf("%d",&t); while(t--) { int x; scanf("%d",&x); printf("%d\n",sum[x]); } return 0; }