[可达鸭四月月赛——入门赛第六场(周六) T4]原初数题解

本题解署名：王胤皓

正文开始

题意

时间限制：1秒内存限制：256M

题目描述

如果一个数字只由若干个不同的质数相乘得到，那么我们就称这个数字为“原初数”。本题中指的数字都是大于 $1$ 的数字。

小可认为，原初数是一切数字的源头。当然，质数本身也是原初数。除了质数以外，比如 $6=2\times 3$ ， $42=2\times 3\times 7$ 等都是原初数。但是 $12=2\times 2\times 3$ ， $8=2\times2\times2$ 灯不是原初数。

例如 $6=2^1\times3^1$ 如果有一个不是原初数的数字，只有 $2$ 和 $3$ 作为质因数，那么这个数字称为 $6$ 的子数。比如 $6$ 的子数有 $12 、 24 、 36$ 等。但是 $15$ 等数字不是 $6$ 的子数。

但是数字是无穷的。于是小可决定把范围限制在 $[2, n]$ 内。然后小可会在这个范围内给你 $m$ 个数字。

如果小可给的数字是原初数，请从小到大输出这个原初数的子数有哪些。当然，这些子数都得在 $[2, n]$ 的范围内。

如果小可给的数字不是原初数，那么输出这个数字的原初数。具体格式见输出描述和样例。

输入描述

第一行两个正整数 $n, m$ ，代表小可划定的范围为 $[2, n]$ ，小可会在这个范围内给你 $m$ 个数字。

第二行 $m$ 个正整数 $a_1,a_2\cdots,a_m$ ，代表小可给你的 $m$ 个数字。

输出描述

对于每个给定的数字，如果它是原初数，那么首先输出 A: ，然后输出这个数字的子数，从小到大排列。

如果这个数字不是原初数，那么首先输出 B: ，然后输出这个数字的原初数。

注意，冒号是英文冒号。冒号后面有一个空格。

每个给定的数字的输出占一行。具体情况参考样例。

样例输入

100 10
2 3 91 24 50 75 12 15 20 100

样例输出

A: 4 8 16 32 64
A: 9 27 81
A:
B: 6
B: 10
B: 15
B: 6
A: 45 75
B: 10
B: 10

提示

如果把原初数分解成质因数相乘的形式，可以发现，每个质数的指数都是 $1$ 。比如 $10=2^1\times5^1$ 。

子数就是在原初数的基础上，某些质因数的指数大于 $1$ 。比如 $10$ 的子数有 $2^3\times5^1,2^2\times5^4$ 等等。

数据范围

对于 $20\%$ 的数据， $2\le n\le20,1\le m\le10$ 。

对于另外 $20\%$ 的数据， $2\le n\le1000,1\le m\le1000$ 。

对于另外 $20\%$ 的数据， $2\le n\le10^4,1\le m\le10^4$ 。

对于另外 $20\%$ 的数据， $2\le n\le2\times10^6,1\le m\le1000$ 。

对于另外 $20\%$ 的数据， $2\le n\le3\times10^6,1\le m\le3\times10^6$ 。

对于 $100\%$ 的数据，保证小可给定的 $m$ 个数字中的原初数的个数不超过 $5\times 10^4$ 。

思路

upd:这题我问的王弘毅老师，王弘毅老师把他代码中的 Euler 函数给我看了看，然后我想了想主函数的内容，然后就 $\colorbox{52C41A}{\color{white}{\texttt{AC}}}$ 了。

这题卡的比较紧，稍不注意就会得到 $\colorbox{052242}{\color{white}{\texttt{TLE}}}$ 的好成绩（作者经历了 $1$ 次 $\colorbox{052242}{\color{white}{\texttt{OLE}}}$ , $4$ 次 $\colorbox{052242}{\color{white}{\texttt{TLE}}}$ , $2$ 次 $\colorbox{052242}{\color{white}{\texttt{MLE}}}$ ， $2$ 次 $\colorbox{9D3DCF}{\color{white}{\texttt{RE}}}$ 和 $2$ 次 $\colorbox{E74C3C}{\color{white}{\texttt{WA}}}$ 才 $\colorbox{52C41A}{\color{white}{\texttt{AC}}}$ 的）。

首先进行一遍欧拉筛，筛出质数，然后顺便打出每个数的原初数是多少：

如果这个数是质数，那么这个数的原初数就是这个数，所以 $f_i=i$ 。
在进行欧拉筛的时候，在遍历质数表的时候，加入一下语句：
- 在判断 $i\bmod prime_j=0$ 的时候，那么 $f_{i\times prime_j}=f_i$ 。
  - 证明：因为 $prime_j$ 是 $i$ 的一个因数，所以不需要再乘，直接相等即可。
- 否则 $f_{i\times prime_j}=f_{i}\times prime_j$ 。
  - 证明：因为 $prime_j$ 不是 $i$ 的一个因数，所以需要再乘，乘起来即可。

进行完之后，用 $3\times10^6$ 个 vector 存储原初数对应的这个原初数的 子数，但是如果 $f_i=i$ ，那么就说明这是个原初数，不统计。

主函数内：
先调用函数。
接下来 $m$ 组：
如果 $f_{a_i}=a_i$ ，那么这个数是一个原初数，输出 A: 和 $ans_{a_i}$ 的全部内容。
否则输出 B: 和 $f_{a_i}$ 。

代码实现

#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,pr[3000005],f[3000005];
bool vis[3000005];
vector<int> ans[3000005];
void Euler(int n){for(int i=2; i<=n; i++){if(!f[i]){pr[cnt++]=i;f[i]=i;}for(int j=0; j<cnt&&i*pr[j]<=n; j++){vis[pr[j]*i]=1;if(i%pr[j]==0){f[i*pr[j]]=f[i];break;}f[i*pr[j]]=f[i]*pr[j];}}for(int i=2; i<=n; i++){if(f[i]==i) continue;ans[f[i]].push_back(i);}
}
int main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);cin>>n>>m;Euler(n);while(m--){int a;cin>>a;if(f[a]==a){cout<<"A: ";for(int i=0; i<ans[a].size()&&ans[a][i]<=n; i++) cout<<ans[a][i]<<" ";cout<<"\n";}else{cout<<"B: ";cout<<f[a]<<"\n";}}return 0;
}