GCD_LCM - Editorial

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:

  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[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';
    }
}

hiiiiii this was my problem :slight_smile:

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 :wave: ,
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 :wave: ,
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).
    here is your modified code.
#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[2] = 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;
}
‘’’
Please help me out I am getting wa on two test cases.