PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Archit Manas
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
Easy
PREREQUISITES:
Number Theory
PROBLEM:
The Chef has been hunting for a machine developed to change numbers in a rather peculiar manner. This machine has a fixed number c associated with it and a changing number X.
In a single step, the Chef can do the following:
- First, choose any positive integer b that is a perfect c-th power of some number (that is, there is some positive integer n such that b = n^c)
- Then, change X \to \dfrac{\text{lcm}(b, X)}{\gcd(b, X)}
He wants to find the minimum number he can change X into by applying these operations alone any number of times (possibly none at all). However, he does not know the exact values of X, c for the machine, but he does have T guesses for what these values might be. For each of these guesses, compute the minimum number Chef can obtain.
EXPLANATION:
We first solve the problem where X contains only one prime factor, i.e. X = p^k for some k \ge 0. Notice the following:
- At any turn, X can only has p as its prime factor. Therefore, our goal is now to reduce the exponent to as small as possible.
- Suppose k = x \cdot c + y, where y = k \mod c. Then we can reduce k to y (by setting b = p^{xc} during the operation), or to c - y (by setting b = p^{(x + 1)c} during the operation). These are the two smallest values to we reduce k into.
Therefore, we can reduce X to p^{\min(k \mod c, c - k \mod c)}.
When X contains multiple prime factors, we can solve for each prime independently and obtain the answer for X.
TIME COMPLEXITY:
Time complexity is O(\sqrt{X} + \log(X) \cdot c) for each test case, where \sqrt{X} comes from factorization of X, and \log(X) \cdot c comes from solving for each prime factor independently for each test case.
SOLUTION:
Setter's Solution
//tt89 ;)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int mod= 1e9+7;
int x,k;
vector<pair<int,int>> arr;
int solve() {
for(int i=2;i<=sqrt(x);i++) {
int c=0;
while (x%i==0) {
x/=i; c++;
}
if(x) arr.push_back({i,c});
}
if(x!=1) arr.push_back({x,1});
int ans=1;
for(int i=0;i<arr.size();i++) {
int n =arr[i].first, c=arr[i].second;
c%=k;
c= min(c,k-c);
ans*= pow(n,c);
}
return ans;
}
signed main() {
fastIO;
int TT=1; cin>>TT;
for(int tt=1;tt<=TT;tt++) {
cin>>x>>k;
arr.clear();
cout<<solve()<<"\n";
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
ll n;
ll a[2001];
ll dp[2001];
void solve(){
ll x,c;cin >> x >> c;
if(c==1){
cout << "1\n";return;
}
ll z=x;
ll y=1;
for(ll i=2; i*i<=x ;i++){
if(z%i==0){
ll d=0;
while(z%i==0) z/=i,d++;
d%=c;
d=min(d,c-d);
for(int j=0; j<d ;j++) y*=i;
}
}
cout << y*z << '\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;while(t--) solve();
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
long long x; int c; cin >> x >> c;
vector<pair<long long, int>> pr;
for (int i = 2; 1LL * i * i <= x; i++) {
if (x % i == 0) {
pr.push_back({i, 0});
while (x % i == 0) {
x /= i;
pr.back().second++;
}
}
}
if (x > 1) {
pr.push_back({x, 1});
}
long long ans = 1;
for (auto &[p, k] : pr) {
k %= c;
k = min(k, c - k);
ans *= pow(p, k);
}
cout << ans << '\n';
}
}
,