2018ICPC南京网络赛 J题 Sum 找规律+数学

题目链接
题意：
定义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("%dn",sum[x]);
}
return 0;
}

最后

以上就是爱撒娇短靴为你收集整理的2018ICPC南京网络赛 J题 Sum 找规律+数学的全部内容，希望文章能够帮你解决2018ICPC南京网络赛 J题 Sum 找规律+数学所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。