2018 icpc 南京站 网络赛 J sum （魔改线性筛法）
题目链接：https://nanti.jisuanke.com/t/30999
A square-free integer is an integer which is indivisible by any square number except 11. For example, 6=2⋅36=2⋅3 is square-free, but 12=22⋅312=22⋅3 is not, because 2222 is a square number. Some integers could be decomposed into product of two square-free integers, there may be more than one decomposition ways. For example, 6=1⋅6=6⋅1=2⋅3=3⋅2,n=ab6=1⋅6=6⋅1=2⋅3=3⋅2,n=ab and n=ban=ba are considered different if a̸=ba̸=b. f(n)f(n) is the number of decomposition ways that n=abn=absuch that aa and bb are square-free integers. The problem is calculating ∑i=1nf(i)∑i=1nf(i).
Input
The first line contains an integer T(T≤20)T(T≤20), denoting the number of test cases.
For each test case, there first line has a integer n(n≤2⋅107)n(n≤2⋅107).
Output
For each test case, print the answer ∑i=1nf(i)∑i=1nf(i).
Hint
∑i=18f(i)=f(1)+⋯+f(8)∑i=18f(i)=f(1)+⋯+f(8)
=1+2+2+1+2+4+2+0=14=1+2+2+1+2+4+2+0=14.
样例输入 复制
样例输出 复制
题目大意：f(x)表示x分解为a*b且a b中均不含平方因子的方案数目（ab ba算两种）
求f(1)+......+f(n)
为什么会想到筛法呢... 因为一个数分解成两个数乘积之后，其中每个数可以继续往下分，也就是说小的数是大的数的一个子情况，像素数筛法一样，可以筛掉一类数
n比较大，考虑线性筛法思维 首先将素数的ans赋值为2（1 pri pri 1）
当筛到i*pri[j]的时候，共有三种情况
1.i%pri[j]!=0 i和pri[j] 对ans [ i*pri[j] ]均产生贡献，结果为两者乘积
2 i中含有pri[j]的一次幂因子 ans[i*pri[j] ]的结果与剔除 pri[j]^2 后的结果相同（只能将pri[j]分别放在a和b中才能保证方案合法）
3 i中含有pri[j]的二次幂因子 怎么分配 a或者b中都会含有平方因子 直接赋值为0
#include<iostream>
#include <cstring>
#define ll long long
using namespace std;
const int maxn=2e7+1;
int prime[maxn];
int tot=0;
int now[maxn];
bool is_prime[maxn];
void init()
{
memset(is_prime,1,sizeof(is_prime));
memset(now,0,sizeof(now));
now[1]=1;
is_prime[1]=0;
for(int i=2;i<maxn;i++)//枚举当前数字
{
if(is_prime[i])
{
now[i]=2;
prime[tot++]=i;
}
for(int j=0;j<tot && 1ll*i*prime[j]<maxn;j++)
{
is_prime[i*prime[j]]=false;
if(i%prime[j]==0)//i为素数pri[j]的倍数
{
int temp=prime[j]*prime[j];
if(i%temp==0)//i中有当前素数的平方因子
{
now[prime[j]*i]=0;
}
else//i中只有当前素数的一个因子
{
now[i*prime[j]]=now[i/prime[j]];
}
break;
}
else
{
now[i*prime[j]]=now[i]*now[prime[j]];
}
}
}
}
int pre[maxn];
void INIT()
{
memset(pre,0,sizeof(pre));
for(int i=1;i<maxn;i++)
{
pre[i]=pre[i-1]+now[i];
}
}
int main()
{
int t,n;
init();
INIT();
//cout<<tot<<endl;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%d\n",pre[n]);
}
return 0;
}
AI生成项目cpp
