多个数的质因数分解
思路：因为每次操作一定会使 x+y 变大或者不变，所以就一直换到不变的情况，而不变的情况中x和y是倍数关系，那我们就将所有的数进行质因数分解，用map<int, vector
例如第三个样例：
5 -> 1
2 -> 2 2 1 1
3 -> 3 2 1 1
ans = 5^1 * 2^2 * 3^3 + 2^2 * 3^2 + 2 * 3 + 2 * 3 + 1 + 1
ans = 540 + 36 + 12 + 2 = 590
优化：比赛当时思路是这样想的，但是最后超时了，就差一些优化（要是过了就有金牌了QAQ）
比如质因数分解，我们在用欧拉筛的时候可以顺便把每个数的最小质因数求出来，之后质因数分解时直接除最小质因数
还有最后的计算，我们可以用一个ans数组，初始化为1，遍历质数次幂vector的时候在每个位置上直接乘就行了
欧拉筛求质数和每个数的最小质因数：
点击查看代码
int prime[100000];
int vis[N];
int euler(int n){
int cnt = 0;
for(int i = 2; i <= n; i ++){
if(!vis[i]) {
vis[i] = i;
prime[cnt ++] = i;
}
for(int j = 0; j < cnt; j ++){
if(i * prime[j] > n) break;
vis[i * prime[j]] = prime[j];
if(i % prime[j] == 0) break;
}
}
return cnt;
}
整体代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define int long long
const int N = 1e6 + 5;
const int mod = 998244353;
int prime[100000];
int vis[N];
int euler(int n){
int cnt = 0;
for(int i = 2; i <= n; i ++){
if(!vis[i]) {
vis[i] = i;
prime[cnt ++] = i;
}
for(int j = 0; j < cnt; j ++){
if(i * prime[j] > n) break;
vis[i * prime[j]] = prime[j];
if(i % prime[j] == 0) break;
}
}
return cnt;
}
int fastpower(int a, int n){
int ans = 1;
while(n){
if(n & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
n >>= 1;
}
return ans;
}
void solve(){
unordered_map<int, vector<int> > mp;
int n; cin >> n;
for(int i = 1; i <= n; i ++){
int a; cin >> a;
while(a != 1){
int p = vis[a];
int cnt = 0;
while(vis[a] == p){
cnt ++;
a /= p;
}
mp[p].push_back(cnt);
}
}
for(auto [p, a] : mp){
cout << p << " -> ";
sort(a.begin(),a.end(),greater<int>());
for(int v : a){
cout << v << " ";
}
cout << "\n";
}
int res[n + 1];
for(int i = 0; i < n; i ++) res[i] = 1;
int ans = 0;
for(auto [p, a] : mp){
sort(a.begin(), a.end(), greater<int>());
for(int i = 0; i < a.size(); i ++){
res[i] = (res[i] * fastpower(p, a[i])) % mod;
}
}
for(int i = 0; i < n; i ++) ans = (ans + res[i]) % mod;
cout << ans << "\n";
}
signed main(){
IOS;
euler(N - 5);
int t = 1;
cin >> t;
while (t --){
solve();
}
return 0;
}