EQUIVALENT Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Utkarsh Gupta
Tester: Satyam, Tejas Pandey
Editorialist: Pratiyush Mishra

DIFFICULTY:

2087

PREREQUISITES:

None

PROBLEM:

Chef calls a pair of integers (A, B) equivalent if there exist some positive integers X and Y such that A^X = B^Y.

Given A and B, determine whether the pair is equivalent or not.

EXPLANATION:

In order for two number A and B to satisfy the relation

A^x = B^y

where x and y are two positive integers, it needs to satisfy the following conditions:
1.) Both the number should have the same prime factors.
2.) The ratio of frequency of each prime factors of the two numbers should be the same.

Thus we would first check if both the numbers have same prime factors and if yes then we would calculate the frequency of each prime factor for the two numbers and then check if each pair of frequencies have the same ratio.

TIME COMPLEXITY:

O(\sqrt{max(A,B)}), for each test case.

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

1 Like

Well, how about this approach?

Keep dividing the numbers until they don’t, or become equal.

Also, can anyone please tell me the time complexity of this solution?

int rec(int a, int b) {
  if (a == b) return 1;
  if (((a % b) != 0) && ((b % a) != 0)) return 0;
  if (a < b) {
    return rec(b / a, a);
  }else return rec(a / b, b);
}
void answer() {
  int a,b;
  cin >> a >> b;
  if (rec(a, b)) cout << "YES" << endl;
  else cout << "NO" << endl;
}

1 Like

Plz SomeBody say why I am getting wrong ans on my this code
I am storing each value of multiple till 10 ki 9 in a set data structure
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
using namespace chrono;

#pragma GCC target (“avx2”)
#pragma GCC optimization (“O3”)
#pragma GCC optimization (“unroll-loops”)
#pragma GCC optimization (“Ofast”)

#define ordered_set tree<int, null_type,less, rb_tree_tag,tree_order_statistics_node_update>
#define fio ios_base::sync_with_stdio(false), cin.tie(NULL),cout.tie(NULL)
#define PI 3.141592653589793238462
#define MOD 1000000007
#define lli long long int
#define INF 1e18
#define nl ‘\n’
#define pb push_back
#define ppb pop_back
#define f first
#define s second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define py cout << “YES” << nl
#define pn cout << “NO” << nl
#define loop(i,a,b) for (int i = a; i <= b; i++)
#define rloop(i,a,b) for (int i = a; i >= b; i–)
#define tc(t) int t; cin >> t; while (t–)
#define prec(n) fixed<<setprecision(n)
#define ini(a, i) memset(a, i, sizeof(a))

#define us unordered_set
#define um unordered_map
#define ll long long
#define ull unsigned long long
#define maxpq priority_queue
#define pii pair<int, int>
#define minpq priority_queue<int, vector, greater >

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x<<" "; _print(x); cerr << endl;
#else
#define debug(x);
#endif

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}
void google(int t) {cout << “Case #” << t << ": ";}
template <class T, class V> void _print(pair <T, V> p);
template void _print(vector v);
template void _print(set v);
template <class T, class V> void _print(map <T, V> v);
template void _print(multiset v);
template <class T, class V> void _print(pair <T, V> p) {cerr << “{”; _print(p.f); cerr << “,”; _print(p.s); cerr << “}”;}
template void _print(vector v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template void _print(set v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template void _print(multiset v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << “]”;}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << “]”;}

vector<vector> pre(int N){
vector<vector> divs(N);
loop(i, 1, N-1){
for(int j=i;j<N;j+=i)
divs[j].pb(i);
}
return divs;
}

vector sieve(int n) {intarr = new intn + 1; vector vect; for (int i = 2; i <= n; i++)if (arr[i] == 0) {vect.push_back(i); for (int j = 2 * i; j <= n; j += i)arr[j] = 1;} return vect;}
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}
ll add(ll x, ll y, ll m) {ll res=x+y; return res>=m ? res-m:res;}
ll mul(ll x, ll y, ll m) {ll res=x
y; return res>=m? res%m:res;}
ll sub(ll x, ll y, ll m) {ll res=x-y; return res<0? res+m:res;}
ll power(ll x, ll y, ll m) {ll res=1; x%=m; while(y){ if (y&1) res=mul(res, x, m); y >>=1; x=mul(x, x, m);} return res;}

void solve(){

tc(t){
    ll a,b;
    cin>>a>>b;
    ll multi=-1;
    set<ll>st1,st2;
    // ll num=multi*a*b;
    ll v1=a;
    ll v2=b;
    if(a%b!=0 && b%a!=0){
        pn;
        continue;
    }
    if(a==b){
        py;
        continue;
    }
    bool flag=false;
    ll t1=a;
    ll t2=b;
    if(min(a,b)==1){
        pn;
        continue;
    }
    while(t1<1e9 && t2<1e9){
        // cout<<a<<" "<<b<<nl;
         t1*=a;
            st1.insert(t1);
        if(st1.find(t2)!=st1.end()){
            flag=true;
            break;
        }
        t2*=b;
        // cout<<a<<" "<<b<<nl;
        st2.insert(t2);
        if(st2.find(t1)!=st2.end()){
            flag=true;
            break;
        }
        
    }
    if(flag){
        py;
    }
    else{
        pn;
    }
}  

}

int main(){
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif

#ifndef ONLINE_JUDGE
freopen(“Error.txt”, “w”, stderr);
#endif

fio;
auto start1 = high_resolution_clock::now();
solve();
auto stop1 = high_resolution_clock::now();
auto duration = duration_cast(stop1 - start1);

#ifndef ONLINE_JUDGE
cerr << "Time: " << duration . count() / 1000 << endl;
#endif
}

The reason it works is because both a and b need to be integer powers of the same integer value. Check out tester 1’s solution. He precomputes the table that for each index i gives the minimum integer j such that i is an integer power of j. Then each test case is O(1).

After the end of the contest I saw that in the editorial and most of the contestants used prime factorization which leads to a time complexity of O(sqrt(max(A, B)) , but I did a much faster solution in O(1) (it got accepted).
My solution:
we need to find if there are two positive integers X and Y such that A^X = B^Y.
Let’s break this down like the following:
A^X = B^Y ==> exp(X * log(A)) = exp(Y * log(B))
==> X * log(A) = Y * log(B)
==> X / Y = log(B) / log(A)
X and Y being integers means that we need to check if log(B) / log(A) is a rational number or not, here is an algorithm to approximate that:

bool is_rational(long double x) {
    x = abs(x);
    for (int i = 0; i < 20; ++i) {
        const auto a = floor(x);
        if (x - a < 1e-8)
            return true;
        x = 1 / (x - a);
    }
    return false;
}

so we output YES if it’s rational and NO otherwise, this solution is O(1) time complexity.
I hope I explained my solution very well, and if there is something wrong about it please feel free to discuss it.
my submission: CodeChef

1 Like

I used this approach too, I think it is as same as “Euclidean algorithm”, so the time complexity should be O(logN)?

def solve() -> None:

    a, b = map(int, input().split())

   

    while a != b:

        mx = max(a, b)

        mn = min(a, b)

        if mx % mn != 0:

            print("NO")

            return

       

        a, b = mn, mx // mn

    print("YES")

why are we dividing the frequency of prime factor then checking if they all have equal ratio?

I did the same thing. Where does my solution go wrong? MY SOLUTION. My solution may be very messy but I am pretty sure I implemented the correct concept.

I came to the same idea at first. However, I had no clue how to check irrationality in python.

same question, is there any solution you found?

How can i write code in Java for Tester1 solution, in c++ he used vector of size long, Can you help me with it

Use int array.

i just did brute force (used 2 loops) and checked all the numbers from 1 to 15 and wasn’t able to solve :joy:

does anybody knows how to compare the maps??? I am trying this sol: find the prime factors; put them in the array , then map and check for the ratios. If equal then YES else NO

vector primeFactors_for_b(ll b){

vector<ll>v;

ll c = 2;

while(b>1){

    if(b%c==0){

        v.push_back(c);

        b/=c;

    }

    else c++;

}

return v;

}

vector primeFactors_for_a(ll a){

vector<ll>v;

ll c = 2;

while(a>1){

    if(a%c==0){

        v.push_back(c);

        a/=c;

    }

    else c++;

}

return v;

}

void solve(){

ll a,b; cin>>a>>b;

vector<ll>a1,b1;

a1 = primeFactors_for_a(a);     //vector function

b1 = primeFactors_for_b(b);     //vector function

map<ll,ll>freq1,freq2;

for(ll i=0; i<a1.size(); i++) freq1[a1[i]]++;

for(ll i=0; i<b1.size(); i++) freq2[b1[i]]++;

if(freq1.size()!=freq2.size()) cout<<"NO"<<endl;

else {

   

}

}

Hi @neel_04 ,
I have implemented same approach you explained in below submission link .
It’s getting WA for some cases, but you can at least benefit from my approach of how to compare the maps :slight_smile:

1 Like

@neel_04 Here, is a better implementation of the above idea. He utilized the idea that : By default, a Map in C++ is sorted in increasing order based on its key .

1 Like

thanks for the help