本文主要是介绍ACM-ICPC 2018 南京赛区网络预赛__J. Sum【欧拉筛法+质因子分解+思维】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
- 1000ms
- 512000K
A square-free integer is an integer which is indivisible by any square number except 1. For example, 6=2⋅3 is square-free, but 12=2^2⋅3 is not, because 2^2 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=ab and n=ba are considered different if a̸=b.f(n) is the number of decomposition ways that n=ab such that a and b are square-free integers. The problem is calculating f(1)+f(2)+...+f(n).
Input
The first line contains an integer T(T≤20), denoting the number of test cases.
For each test case, there first line has a integer n(n≤2⋅10^7).
Output
For each test case, print the answer f(1)+f(2)+...+f(n) .
Hint
∑f(i)=f(1)+⋯+f(8)
=1+2+2+1+2+4+2+0=14=1+2+2+1+2+4+2+0=14.
样例输入
2
5
8样例输出
8
14题目来源
ACM-ICPC 2018 南京赛区网络预赛
题目大意：f(n)定义为n=a*b这样分解的式子数，其中a和b不能包含平方因子。当a!=b时n=a*b和n=b*a视为两个式子。t 组测试，n表示所求结果为 f(1)+f(2)+f(3)+...+f(n)
题解：有如下结论
1.若i是素数则f(i)=2
2.若i的某个质因子个数超过2，则f(i)=0。这个结论很好想，如果有大于2个相同质因子，那么对于i的每个分解 i=a*b，a和b中必定有一个数含平方因子
3.若i=a*b且a和b不含相同因子即可，那么f(i)=f(a)*f(b)
4.若i的质因子x的个数为2，f(i)=f(i/(x*x))即为去掉平方因子的个数
打表用到了欧拉筛法
AC的C++代码：
#include<iostream>using namespace std;
const int N=2e7+5;int prime[N];//存储连续素数，prime[0]表示连续素数的个数
bool vis[N];
int f[N];//结果void solve()
{f[1]=1;for(int i=2;i<N;i++){if(!vis[i]){prime[++prime[0]]=i;//存储这个素数 f[i]=2;//素数的结果为2 }for(int j=1;j<=prime[0]&&prime[j]*i<N;j++){int x=prime[j]*i;vis[x]=true;//标记x为合数 if(i%prime[j])//若i=a*b且a和b不含相同因子即可，那么f(i)=f(a)*f(b)f[x]=f[prime[j]]*f[i];else{//如果prime[j]是i的最小质因子 if(i%(prime[j]*prime[j])==0)//如果x的某个质因子个数超过2则f[i]=0 f[x]=0;else//如果x的某个质因子个数为2，则答案为去掉平方项的结果 f[x]=f[x/(prime[j]*prime[j])];break;//欧拉筛法保证每个合数只被它的最小质因子筛去，因此要跳出 }}}//前缀和 for(int i=1;i<N;i++)f[i]+=f[i-1];
}int main()
{int t,n;solve();scanf("%d",&t);while(t--){scanf("%d",&n);printf("%d\n",f[n]);}return 0;
}解法二
#include<iostream>using namespace std;typedef long long ll;
const int N=20000007;int prime[N+1];
ll f[N+1];void solve(int n)
{f[1]=1;for(int i=2;i<=n;i++){if(!prime[i]){prime[++prime[0]]=i;f[i]=2;}for(int j=1;j<=prime[0]&&prime[j]<=n/i;j++){prime[i*prime[j]]=1;if(i%prime[j]){f[i*prime[j]]=f[i]*2;}else//i%prime[j]==0{if((i/prime[j])%prime[j]==0)f[i*prime[j]]=0;elsef[i*prime[j]]=f[i/prime[j]];break;}}}for(int i=2;i<=n;i++)f[i]+=f[i-1];
}int main()
{int t,n;solve(N);scanf("%d",&t);while(t--){scanf("%d",&n);printf("%lld\n",f[n]);}return 0;
}
这篇关于ACM-ICPC 2018 南京赛区网络预赛__J. Sum【欧拉筛法+质因子分解+思维】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
