Codeforces Round 1083 (Div. 2)——CF-2205-B. Simons and Cakes for Success（如何求一个数全部素因子的乘积？）

题目大意

题目描述
给定一个整数 $n$，要求找到最小的正整数 $k$，使得 $n$ 能够整除 $k^n$（即 $n$ 是 $k^n$ 的因数）。
数据保证在给定范围内始终存在答案。

输入格式
第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。
接下来的 $t$ 行，每行包含一个整数 $n$（$2 \le n \le 10^9$），表示题目给定的数值。

输出格式
对于每个测试用例，输出一行一个整数，表示满足条件的最小正整数 $k$。

样例输入

4
8
12
369
55635800

样例输出

2
6
123
2090

样例解释
在第一个测试用例中（$n = 8$）：
当 $k = 1$ 时，$1^8 = 1$，$8$ 不是 $1$ 的因数；
当 $k = 2$ 时，$2^8 = 256$，$8$ 是 $256$ 的因数（因为 $256 = 8 \times 32$）。
因此，最小可能的 $k$ 为 $2$。

在第二个测试用例中（$n = 12$）：
最小的 $k$ 为 $6$，因为 $12$ 是 $6^{12} = 2176782336$ 的因数（因为 $2176782336 = 12 \times 181398528$）。

思路讲解

不难发现，答案就是 N 的所有素因子的乘积。

不过对于我来说，一个难点是怎么样求，就是N的所有素因子的乘积是多少。（在这道题目的数据范围限制下）

我们这里就用到了一个小trick，就是一个数啊，大于根号N的素因子，有的话只有一个。因此我们就不断的把小的素因子全部都给除掉，那么剩下的一个素因子就是最大的了。（而且这个大于根号N的素因子显然不可能被乘很多遍）

ll opN=N;
for (auto p1:primes) {
    if (p1*p1>N) {
        break;
    }
    if (opN%p1==0) {
        res*=p1;
        while (opN%p1==0) {
            opN/=p1;
        }
    }
}
res*=opN;
cout<<res<<"\n";

AC代码

AC

https://codeforces.com/contest/2205/submission/364837938

源代码

/**
 * Problem: B. Simons and Cakes for Success
 * Contest: Codeforces Round 1083 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2205/problem/B
 * Created: 2026-02-28 20:08:34
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */
//  minp[i] 存储的是i的最小素因数
// https://www.luogu.com.cn/record/221554377
vector<ll> minp,primes;
void sieve(ll n){
    minp.assign(n+5,0);
    // minp[1]=1;  // 加了这句话可能把 1 误判成素数，要小心
    for(int i=2;i<=n;++i){
        if(minp[i]==0){		// 是素数
            minp[i]=i;
            primes.push_back(i);
        }
        for(auto p:primes){
            if(i*p>n){	// 超范围了
                break;
            }
            minp[i*p]=p;
            // 为了保证每个合数都只被其【最小的】那个质因数标记一次 break
            // i * p_next = (p * k) * p_next 最小的应该是p
            if(p==minp[i]){
                break;
            }
        }
    }
}

void Solve() {
    ll N;
    cin >> N;
    ll res=1;
    ll opN=N;
    for (auto p1:primes) {
        if (p1*p1>N) {
            break;
        }
        if (opN%p1==0) {
            res*=p1;
            while (opN%p1==0) {
                opN/=p1;
            }
        }
    }
    res*=opN;
    cout<<res<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    sieve(1e6);
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/contest/2205/submission/364837938

*/

心路历程（WA，TLE，MLE……）