 # GCD_LCM - Editorial

Setter: Archit Manas
Tester: Harris Leung
Editorialist: Trung Dang

Easy

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:

1. 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.
2. 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;
ll dp;
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';
}
}


hiiiiii this was my problem 23 Likes

can anyone help finding which testcases I’m missing here
https://www.codechef.com/viewsolution/63092799
#include <bits/stdc++.h>
using namespace std;

using P = pair<int, int>;
#define f first
#define s second

using ll = long long;

ll find(ll x,ll c,ll n)
{
ll b=(ll)pow(n,c);
return b;
}

void solve(){
ll x,c;
cin>>x>>c;
if(x==1 || c==1)
{
cout<<1<<endl;
return ;
}
bool flag=false;
while(!flag)
{

      for(ll i=2;i<=x;i++)
{

ll b=find(x,c,i);
if(b>x)
{
cout<<x<<endl;
return ;
}
ll gcd=__gcd(b,x);
//  if(gcd!=1)
//{
ll curr=(b*x)/(gcd*gcd);
if(curr<x)
{

x=curr;
if(x==1)
{
cout<<1<<endl;
return ;
}
break;
}
//}

}
}
// now lcm(b,X)*gcd(b,X)=b*X;
// given y=lcm(b,X)/gcd(b,X)=(b*x)/(gcd(b,X)*gcd(b,X))
// now  for 20  and 4
// given 1^4 ,2^4,  b=n^c
//  16 can be equal to 2^4
//  lcm(16,20)/gcd(16,20)=80/4=20 so it can't be smaller than 20
// (b*x)/(gcd(b,X)*gcd(b,X))
//  here if gcd(b,X) is between the
// like 20*16/(4*4)
// by taking example  170 3
// for  lcm(170,125)/gcd(170,125)
// drop it down to


}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;

while(t–){
solve();

}

}

https://www.codechef.com/viewsolution/63098086

How did this solution pass the TCs? It’s literally brute force.

3 Likes

Whats wrong in this?

 while (tc-- > 0) {
long a = sc.nextInt();
long b = sc.nextInt();

long ans = 1;
long f = 2;

if(b!=1)
{

while (a > 1) {
long count = 0;
while (a % f == 0) {
a /= f;
count += 1;
}

long mod = count % b;

if (count % b != 0) {
ans = ans * (long)Math.pow(f, Math.min(mod, b - mod));
}
f += 1;

}
}
sb.append(ans);
sb.append("\n");
}

System.out.println(sb);

@kratos_46 even i did the same in c++ first but it is giving me WA why?

The problem was very nice.

1 Like

https://www.codechef.com/viewsolution/63050209
GREEDY,BRUTEFORCE {NO PRIME FACTORIZATION}

why the c++ version of it is getting TLE and WA ?
link : Solution: 63117657 | CodeChef

Hey @sourabh_0123 ,
your code is printing garbage value in test case
1
999999999 7
Try to solve this and TLE is due to case when c=1 ,
Your code is running exactly n=(10^3) * x times.this is what a issue for a TLE.

1 Like

What’s wrong in this submission? I reduced x by the formula mentioned in the question. It seems similar to the finding min(k mod c,c−k mod c). But getting WA in all test cases.

https://www.codechef.com/viewsolution/63131948

Hey @rf_faisal ,
You did a lot of things wrong (silly mistakes).

1. According to the editorial k should not be >=c because k = c*x + y so we can Calculate for min x. like if we want k = xc we do prime p^((x+1)c) and if we want k = y we do p ^ (xc).
Also you don’t have to multiply the x with (lcm(b,x)/gcd(b,x)) you only need to multiply the specific p with some min power we calculated (because we already reduced that power).
#include<bits/stdc++.h>
using namespace std;
#define int long long

int power(int a, int n){
int res = 1;
while(n){
if(n&1) res *= a;
a *= a;
n >>= 1;
}
return res;
}

signed main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int tc; cin>>tc;
while(tc--){
int x, c; cin>>x>>c;
map<int, int> mp;

int x_ = x, cnt = 0;
while(x_%2 == 0){
x_ /= 2;
++cnt;
}
if(cnt)
mp = cnt;

for(int i=3; i*i<=x_; i++){
cnt = 0;
while(x_%i == 0){
x_ /= i;
++cnt;
}
if(cnt) mp[i] = cnt;
}
if(x_>2)
mp[x_] = 1;
x=1;
for(auto it: mp){
int n = it.first, ss = it.second;
ss%=c;
int k = min(ss,(c-ss)%c);
int b = power(n, k);
x *= b;
}
cout<<x<<'\n';
}
}
`
1 Like

‘’’#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll i, t, x, c, mn;
ll power(ll a, ll b)
{
ll ans = 1;
while (b > 0)
{
if (b & 1)
{
ans = ans * a;
}
a = a * a;
b >>= 1;
}
return ans;
}
void solve()
{
cin >> x >> c;
if (c == 1)
{
mn = 1;
cout << mn << endl;
return;
}
i = 1;
ll num, g, ans;
mn = x;
num = 1;
while (num<=x)
{
num = power(i, c);
g = __gcd(num, x);
ans = (num * x) / (g * g);
if (ans < mn)
mn = ans;
i++;
}
cout << mn << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> t;
while (t–)
{
solve();
}
return 0;
}
‘’’