L - Non-Prime Factors （质数筛选+因子分解）
in many programming competitions, we are asked to find (or count the number of) prime factors of an integer i. this is boring. this time, let’s count the number of non-prime factors of an integer i, denoted as npf(i).
for example, integer 100 has the following nine factors: {1,2,4,5,10,20,25,50,100}. the two which are underlined are prime factors of 100 and the rest are non-prime factors. therefore, npf(100) = 7.
input
the first line contains an integer q (1≤q≤3⋅10^6) denoting the number of queries. each of the next q lines contains one integer i (2≤i≤2⋅10^6).
output
for each query i, print the value of npf(i).
warning
the i/o files are large. please use fast i/o methods.
| sample input 1 | sample output 1 |
|---|---|
4 100 13 12 2018 |
7 1 4 2 |
题目大意：第一行给一个q，代表q次查询，接下来q行，每行一个整数i，求npf（i）
拿样例100来说，100的因子有（1,2,4,5,10,20,25,50,100）共9个，其中2和5是质数（一个大于1的自然数，除了1和它本身外，不能被其他自然数整除），应去掉，剩下7个。
所以npf（100）= 7
拿样例13来说，13的因子有（1,13）共2个，其中13是质数，去掉后，剩下1个。
所以npf（13）= 1
解题思路：1.先预处理出1-2*10^6的质数。可以用eratosthenes筛法，时间复杂度o(nloglogn)（某位网友说的）
2.预处理答案，先看代码：
for(int i = 1; i <= 2000000; ++i){
int rt = 2000000/i;
for(int j = i; j <= rt; ++j){
if(vis[i]){//非质数
++ans[i*j];
}
if(vis[j] && i!=j){
++ans[i*j];
}
}
}
第一个for循环，表示1到2*10^6的数。
第二个for循环，对于当前的数i，对 i 到 i*rt 进行处理
举个栗子，对于100来说，ans【100】初始化是0
第一个循环到1时，
在第二个循环中：判断1是非质数，第一个if中必然会有1*100=100，即ans【100】++；（100<rt,必然出现）
第二个if中会出现j=100，100是非质数，又100*1=100，即ans【100】++；
tip：当i=100时，j 从100开始累加而且 j 不会回溯，所以100=1*100这一种分解方法会在i=1的时候处理出来
即ans【100】+=2；
第一个循环到2时：
在第二个循环中：第一个if 判断2是质数，跳过（相当于把2这个因子剔除了，即没有加入答案中）
第二个if j=50时,50是非质数，又50*2=100，所以ans【100】++；
第一个循环到4时：
在第二个循环中：第一个if 判断4是非质数，4*25=100,ans【100】++；
第二个if j=25时,25是非质数，25*4=100，所以ans【100】++；
第一个循环到5时：
在第二个循环中：第一个if 判断5是质数，跳过，
第二个if j=20时,20是非质数，20*5=100，所以ans【100】++；
第一个循环到10时：
在第二个循环中：第一个if 判断10是非质数，10*10=100，ans【100】++；
第二个if j=10时,10是非质数，但是i=j，跳过（相同因子处理一次即可，在第一个if处理了）
第一个循环到20时：20*5=100，但是5不会出现，因为j是从20开始不断累加，ans【100】已经处理结束了，从上面分析可以看出ans【100】=7；
类似的，每个答案都可以在这2个循环中处理出来。
时间上：当i=1来说，rt=2*10^6，j会从1加到2*10^6
当i=2，rt=10^6， j会从2加到10^6；
......
当i=10，rt=2*10^5，j会从10加到2*10^5（此时数量级已经降了一级）
...
当i=100，rt=2*10^4，j会从1加到2*10^4
....
当i=1000，rt=2*10^3，j会从1000加到2000（共1000次）
.....
当i=sqrt（2*10^6） rt=i，第二层循环直接跳过，后面一样，都是1次
把它们加起来，大概也就10^7左右（目测估计法算的）
预处理10^6左右，q个问题3*10^6，加起来数量级也在10^7
某位大佬说10^7的数量级一般都能在1s跑完，要看测评机
一开始我是对每次枚举每个数的因数（1-sqrt（n）），然后想办法优化，结果都是超时....（(╯‵□′)╯︵┻━┻）
启示：优化的时候想想办法让回溯的次数少一点。
ac代码：
#include <iostream>
#include <stdio.h>
#include <cmath>
using namespace std;
bool vis[2000005];
int ans[2000005];
void init()
{
//开始筛，vis=1表示该数不是质数
vis[1]=1;
int m=sqrt(2000002+0.5);
for(int i=2;i<=m;++i)
if(!vis[i]) for(int j=i*i;j<=2000002;j+=i) vis[j]=1;
//筛选结束
for(int i = 1; i <= 2000000; ++i){
int rt = 2000000/i;
for(int j = i; j <= rt; ++j){
if(vis[i]){//非质数
++ans[i*j];
}
if(vis[j] && i!=j){
++ans[i*j];
}
}
}
}
int main()
{
init();
int q;
scanf("%d",&q);
while(q--)
{
int n;
scanf("%d",&n);
printf("%d\n",ans[n]);
}
return 0;
}