Header Ads Widget

Chef and Prime Divisors | codechef solution

Rajnish Tripathi 12:23

You are given two positive integers – A and B. You have to check whether A is divisible by all the prime divisors of B.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

For each test case, you are given two space separated integers – A and B.

Output

For each test case, output "Yes" (without quotes) if A contains all prime divisors of B, otherwise print "No".

Constraints

  • 1 ≤ T ≤ 104
  • 1 ≤ A, B ≤ 1018

Subtasks

  • Subtask 1 (20 points):1 ≤ B ≤ 107
  • Subtask 2 (30 points):1 ≤ A ≤ 107
  • Subtask 3 (50 points): Original constraints

Sample 1:

Input
Output
3
120 75
128 16
7 8
Yes
Yes
No

Explanation:

Example case 1. In the first case 120 = 23*3*5 and 75 = 3*52. 120 is divisible by both 3 and 5. Hence, we will print "Yes"

Example case 2. In the second case both 128 and 16 are powers of two. Hence, the answer is "Yes"

Example case 3. In the third case 8 is power of two and 7 is not divisible by 2. So, the answer is "No"

 Code(C++):-

#include <bits/stdc++.h>
using namespace std;
#define ll long long int

int main()
{
ll t;
cin >> t;
while (t--)
{
ll a, b;
cin >> a >> b;
ll GCD = __gcd(a, b);
while (b > 1 && GCD > 1)
{
b /= GCD;
GCD = __gcd(a, b);
}
if (b > 1)
{
cout << "No\n";
}
else
{
cout << "Yes\n";
}
}
return 0;
}

Code(JAVA):-
import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
public static long gcd(long n,long m)
{
while(n!=0&&m!=0)
         {
         if(n>m)
         n=n%m;
         else
         m=m%n;
         }
        if(n==0)
         n=m;
        return n;
}
    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t=Integer.parseInt(br.readLine());
        long n,m;
        while(t-->0)
        {
         String s[]=br.readLine().split(" ");
         n=Long.parseLong(s[0]);
         m=Long.parseLong(s[1]);
         while(gcd(n,m)>1)
         {
         n=gcd(n,m);
         m/=n;
         }
         if(m==1)
         System.out.println("Yes");
         else
         System.out.println("No");
        }
    }
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags:

Post a Comment

0 Comments