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 |
7 |
题目大意：第一行给一个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 = ; i <= ; ++i){
int rt = /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[];
int ans[];
void init()
{
//开始筛，vis=1表示该数不是质数
vis[]=;
int m=sqrt(+0.5);
for(int i=;i<=m;++i)
if(!vis[i]) for(int j=i*i;j<=;j+=i) vis[j]=;
//筛选结束
for(int i = ; i <= ; ++i){
int rt = /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 ;
}