首页 > > 程序设计 > C/C++ >

L - Non-Prime Factors （质数筛选+因子分解）

2019-04-20 08:52:24来源：博客园阅读 ()

In many programming competitions, we are asked to find (or count the number of) Prime Factors of an integer $i$

For example, integer $100$

Input

The first line contains an integer $Q$

Output

For each query $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;
}