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; }