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 100has the following nine factors: {
- 1,2,4,5,10,20,25,50,100
- }. The two which are underlined are prime factors of 100and the REST are non-prime factors. Therefore, NPF(100) = 7.
- Input
- The first line contains an integer Q(1≤Q≤310^6) denoting the number of queries. Each of the next Qlines contains one integer i(2≤i≤210^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 这个因子剔除了, 即没有加入答案中)
第二个 ifj=50 时, 50 是非质数, 又 50*2=100, 所以 ans[100] ++;
第一个循环到 4 时:
在第二个循环中: 第一个 if 判断 4 是非质数, 4*25=100,ans[100] ++;
第二个 ifj=25 时, 25 是非质数, 25*4=100, 所以 ans[100] ++;
第一个循环到 5 时:
在第二个循环中: 第一个 if 判断 5 是质数, 跳过,
第二个 ifj=20 时, 20 是非质数, 20*5=100, 所以 ans[100] ++;
第一个循环到 10 时:
在第二个循环中: 第一个 if 判断 10 是非质数, 10*10=100,ans[100] ++;
第二个 ifj=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;
- }
来源: http://www.bubuko.com/infodetail-3028620.html