মোরসালিনের সিপি ব্লগ: Another Problem About Dividing Numbers

Friday 11 June 2021

Another Problem About Dividing Numbers :: Codeforces Round 725 D

Problem link

In this problem you will be given two integer number a and b. You need to make a and b equal in exactly k operation(s). In one operation you can either,

Take an integer $c$ ( $c > 1$ and $a$ should be divisible by $c$ ) and replace $a$ with $\frac{a}{c}$
Take an integer $c$

c > 1

b

should be divisible by

c

b

\frac{b}{c}

Observations: If we at least need x moves to make a and b equal and we have at most y moves which is total number of moves we can make in total. A move is choosing such a C discussing above. Then we can also make a and b equal by x+1,x+2,x+3.......y-2,y-1,y moves. [for better understanding a paperwork may help]

Explanation:

For finding the minimum number of moves to make a and b (if a!=b) are equal will be 1 or 2.

>>if gcd(a,b)==min(a,b) then it will be 1.

lets say, a=36 and b=12;

gcd(36,12) = min(36,12) = 12

we can make a=12 by dividing 36 by 3 in one move.

>>if gcd(a,b)!=min(a,b) then it will be 2. Because we need to divide both a and b to make equal to its gcd.

For finding the at most moves we have, we had to find number of prime factors both for a and b. because at most we can divide them until they left any prime factors.

For calculating the Number of prime factors. we will be needed prime numbers. For this purpose a simple sieve will work fine.

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define int long long
#define IOS ios::sync_with_stdio(false);
int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
const int maxn=100005;
bitset<maxn+5>bs;
vector<int> prime;
void seive(){
  bs.set();
  bs[0]=0;
  bs[1]=0;
  for(int i=2;i<maxn;i++){
    if(bs[i]){
      prime.pb(i);
      for(int j = i*i; j<maxn;j+=i)bs[j]=0;
    }
  }
}
///solution
void solution(){
    int a,b,k;
    cin>>a>>b>>k;
    if(a==b && k==1){
        cout << "NO\n";
        return;
    }
    int cnta=0,cntb=0,now=a;
    for(auto it:prime){
      if(it*it>now){
        break;
      }
      while(now%it == 0){
        now/=it;
        cnta++;
      }
    }
    if(now>1)cnta++;
    now=b;
    for(auto it:prime){
      if(it*it>now )break;
      while(now%it == 0){
        now/=it;
        cntb++;
      }
    }
    if(now>1)cntb++;

    int x=gcd(a,b);
    int atmost=cnta+cntb,least=0;
    if(x==min(a,b))least=1;
    else least=2;
    if(least<=k && atmost>=k){
      cout << "YES\n";
    }
    else cout << "NO\n";
}
signed main()
{
  IOS
    int t;
    t=1;
    seive();
    cin>>t;
    while(t--){
        solution();
    }
    return 0;
}