题解：CF2205B Simons and Cakes for Success

Yang_Fane · 2026-03-08 08:19:09 · 题解

题目大意

你需要找到最小的正整数 k ，使得 n 能整除 k^n 。

思路

这个代码的思路是：取 n 的所有不同质因子，乘起来得到 k 。
比如 n = 12 = 2^2 \times 3 ，质因子集合是 \{ 2, 3 \} ，乘积 2 \times 3 = 6 即为所求。

这个思路对于 n 是质数时仍然可行：
例 n = 5 ，质因子集合是 \{ 5 \} ，得 k = 5 ，检查 5^5 被 5 整除（显然成立）。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int N=1e5+10;
int t,v[N],len;
bool vis[N];
void solve(int n){
    vis[0]=vis[1]=1;
    for(int i=2;i<=n;i++){
        if(vis[i]==0){
            v[++len]=i;
        }
        for(int j=1;j<=len && i*v[j]<=n;j++){
            vis[i*v[j]]=1;
            if(i%v[j]==0){
                break;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    solve(31623);//具体为什么是31623，见大佬Q_E_D_的题解 
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int ans=1;
        for(int i=1;i<=len;i++){
            if(n%v[i]==0){
                ans*=v[i];
                while(n%v[i]==0){
                    n/=v[i];
                }
            }
        }
        ans*=n;
        cout<<ans<<"\n";
    }
    return 0;
}

完结撒花