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

本题解署名：王胤皓

正文开始

题意

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

题目描述

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

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

例如 $6=2^1\times 3^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\times 5^1$。

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

数据范围

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

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

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

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

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

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

思路

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

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

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

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

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

主函数内：
先调用函数。
接下来 $m$ 组：
如果 $f_{a_i}=a_i$，那么这个数是一个原初数，输出 A: 和 $an{s}_{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;
}

三连一下再走吧~