Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Prime Factor Division CodeChef Solution
Problem -Prime Factor Division CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Prime Factor Division CodeChef Solution in C++17
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t; cin>>t;
while(t--){
long long int a,b;
cin>>a>>b;
long long int g=__gcd(a,b);;
while(b!=1){
g=__gcd(a,b);
b=b/g;
if(g==1){
break;
}
}
if(g==1 && b!=1){
cout<<"NO"<<endl;
}else{
cout<<"YES"<<endl;
}
}
return 0;
}Prime Factor Division CodeChef Solution in C++14
#include <bits/stdc++.h>
//for policy based ds //p.order_of_key() -> returns index of value //*p.find_by_order(3) ->value at index
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>
#include <functional> // for less
using namespace __gnu_pbds; //for policy based ds
using namespace std;
#define int long long
#define pii pair<int, int>
#define vi vector<int>
#define maxHeap priority_queue<int>;
#define minHeap priority_queue<int, vi, greater<int>>
#define mod 1000000007
#define inf 1e18
#define rep(i, s, n) for (int i = s; i < n; i++)
#define sp(ans, pre) fixed << setprecision(pre) << y
#define pb push_back
#define srt(v) sort(v.begin(), v.end())
#define all(v) begin(v), end(v)
#define inputArr(i, arr) \
for (int &i : arr) \
cin >> i;
#define ll long long
#define ull unsigned long long
#define lld long double
#define kickPrint(tt) cout << "Case #" << tt << ": "
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
time_t Begin;
//////////////////Debug///////////////
#define debug(x) \
cout << #x << " "; \
_print(x); \
cout << endl;
void _print(ll t)
{
cout << t;
}
//void _print(int t) {cout << t;}
void _print(string t) { cout << t; }
void _print(char t) { cout << t; }
void _print(lld t) { cout << t; }
void _print(double t) { cout << t; }
void _print(ull t) { cout << t; }
void display(ll a[], ll n)
{
for (ll i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
template <class T, class V>
void _print(pair<T, V> p);
template <class T>
void _print(vector<T> v);
template <class T>
void _print(set<T> v);
template <class T, class V>
void _print(map<T, V> v);
template <class T>
void _print(multiset<T> v);
template <class T, class V>
void _print(pair<T, V> p)
{
cout << "{";
_print(p.ff);
cout << ",";
_print(p.ss);
cout << "}";
}
template <class T>
void _print(vector<T> v)
{
cout << "[ ";
for (T i : v)
{
_print(i);
cout << " ";
}
cout << "]";
}
template <class T>
void _print(set<T> v)
{
cout << "[ ";
for (T i : v)
{
_print(i);
cout << " ";
}
cout << "]";
}
template <class T>
void _print(multiset<T> v)
{
cout << "[ ";
for (T i : v)
{
_print(i);
cout << " ";
}
cout << "]";
}
template <class T, class V>
void _print(map<T, V> v)
{
cout << "[ ";
for (auto i : v)
{
_print(i);
cout << " ";
}
cout << "]";
}
template <typename T, typename U>
inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
void init()
{
Begin = clock();
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
void timeTaken()
{
#ifndef ONLINE_JUDGE
double time_taken = double(clock() - Begin) / double(CLOCKS_PER_SEC);
cout << "Execution Time: " << fixed << setprecision(5) << time_taken << "s\n";
#endif
}
vector<int> computeLps(string s, int M)
{
int len = 0;
vector<int> lps(M + 20);
lps[0] = 0;
int i = 1;
while (i < M)
{
if (s[i] == s[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if (len != 0)
{
len = lps[len - 1];
}
else
{
lps[i] = 0;
i++;
}
}
}
// debug(len);
return lps;
}
int ceiling(int x, int y)
{
int res = x / y;
if (x % y)
{
if (x >= 0)
res++;
}
return res;
}
vector<vector<int>> makePrefix(vector<vector<int>> &grid)
{
int n = grid.size(), m = grid[0].size();
vector<vector<int>> prefix(n + 1, vector<int>(m + 1));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
prefix[i + 1][j + 1] = grid[i][j] + prefix[i][j + 1] + prefix[i + 1][j] - prefix[i][j];
}
}
return prefix;
}
int query(int x1, int y1, int x2, int y2, vector<vector<int>> &prefix)
{
// cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
// cout << "query: " << prefix[x2 + 1][y2 + 1] << " " << prefix[x2 + 1][y1] << " " << prefix[x1][y2 + 1] << " " << prefix[x1][y2] << endl;
return prefix[x2 + 1][y2 + 1] - prefix[x2 + 1][y1] - prefix[x1][y2 + 1] + prefix[x1][y1];
}
int toInt(string &s)
{
int res = 0;
for (char c : s)
res = res * 10 + (c - '0');
return res;
}
bool isValid(int i, int j, int n, int m)
{
return i >= 0 && i < n && j >= 0 && j < m;
}
int dx[] = {-1, 0, 0, 1};
int dy[] = {0, 1, -1, 0};
int moduloExponentiation(int a, int b, int m)
{
if (b == 0)
return 1;
int res = moduloExponentiation(a, b / 2, m);
res = (res * res) % m;
if (b % 2)
res = (res * a) % m;
return res;
}
int32_t main()
{
init();
//--------------------
int t = 1;
cin >> t;
for (int tt = 1; tt <= t; tt++)
{
int a, b;
cin >> a >> b;
int pre = b;
while (b != 1)
{
int g = __gcd(a, b);
b /= g;
if (b == pre)
break;
pre = b;
}
cout << (b == 1 ? "YES\n" : "NO\n");
}
//---------------------------
timeTaken();
return 0;
}Prime Factor Division CodeChef Solution in PYTH 3
# cook your dish here
import math
n=int(input())
for i in range(1,n+1):
a,b=map(int,input().split())
c=0
d=pow(a,max(a,b),b)
if(d==0):
print("YES")
else:
print("NO")Prime Factor Division CodeChef Solution in C
#include <stdio.h>
// C++ program to find GCD of two numbers
// Recursive function to return gcd of a and b in single line
long high1(long num1, long num2)
{
return num2== 0 ? num1: high1(num2, num1 % num2);
}
int main()
{
int test;
scanf("%d",&test);
for(int i=0;i<test;i++)
{
long num1,num2;
scanf("%ld %ld",&num1,&num2);
long maths = high1(num1,num2);
while(maths!=1)
{
num2/=maths;
maths = high1(maths,num2);
}
if(num2!=1){
printf("NO \n");
}
else
printf("YES \n");
}
return 0;
}
Prime Factor Division CodeChef Solution in JAVA
import java.io.*;
import java.util.*;
class Codechef
{
static void BFS(ArrayList<ArrayList<Integer>> adj,int s, boolean[] visited)
{
Queue<Integer> q=new LinkedList<>();
visited[s] = true;
q.add(s);
while(q.isEmpty()==false)
{
int u = q.poll();
for(int v:adj.get(u)){
if(visited[v]==false){
visited[v]=true;
q.add(v);
}
}
}
}
static int BFS(ArrayList<ArrayList<Integer>> adj,pair s, boolean[] visited,int ar[],int m)
{
Queue<pair> q=new LinkedList<>();
visited[s.a] = true;
q.add(s);
int count=0;
while(q.isEmpty()==false)
{
pair u = q.poll();
// if(adj.get(u.a).size()==0)
// count++;
boolean end=true;
for(int v:adj.get(u.a)){
if(visited[v]==false){
visited[v]=true;
end=false;
int cat=ar[v]==0?0:ar[v]+u.b;
if(cat>m)
continue;
q.add(new pair(v, cat));
// System.out.print("--"+v+" "+cat+"--");
}
}
if(end)
count++;
// System.out.println(u.a+" "+adj.get(u.a).size()+" count "+count);
}
return count;
}
static void addEdge(ArrayList<ArrayList<Integer>> adj, int u, int v)
{
adj.get(u).add(v);
adj.get(v).add(u);
}
static void ruffleSort(long[] a) {
int n=a.length;
Random random = new Random();
for (int i=0; i<n; i++) {
int oi=random.nextInt(n);
long temp=a[oi];
a[oi]=a[i]; a[i]=temp;
}
Arrays.sort(a);
}
static void ruffleSort(int[] a) {
int n=a.length;
Random random = new Random();
for (int i=0; i<n; i++) {
int oi=random.nextInt(n);
int temp=a[oi];
a[oi]=a[i]; a[i]=temp;
}
Arrays.sort(a);
}
public static int Lcm(int a,int b)
{ int max=Math.max(a,b);
for(int i=1;;i++)
{
if((max*i)%a==0&&(max*i)%b==0)
return (max*i);
}
}
static void sieve(int n,boolean prime[])
{
// boolean prime[] = new boolean[n + 1];
for (int i = 0; i <= n; i++)
prime[i] = true;
for (int p = 2; p * p <= n; p++) {
if (prime[p] == true) {
for (int i = p * p; i <= n; i =i+ p)
prime[i] = false;
}
}
}
// public static String run(int ar[],int n)
// {
// }
public static int upperbound(int s,int e, long ar[],long x)
{
int res=-1;
while(s<=e)
{ int mid=((s-e)/2)+e;
if(ar[mid]>x)
{e=mid-1;res=mid;}
else if(ar[mid]<x)
{s=mid+1;}
else
{e=mid-1;res=mid;
if(mid>0&&ar[mid]==ar[mid-1])
e=mid-1;
else
break;
}
}
return res;
}
public static long lowerbound(int s,int e, long ar[],long x)
{
long res=-1;
while(s<=e)
{ int mid=((s-e)/2)+e;
if(ar[mid]>x)
{e=mid-1;}
else if(ar[mid]<x)
{s=mid+1;res=mid;}
else
{res=mid;
if(mid+1<ar.length&&ar[mid]==ar[mid+1])
s=mid+1;
else
break;}
}
return res;
}
static long modulo=1000000007;
public static long power(long a, long b)
{
if(b==0) return 1;
long temp=power(a,b/2)%modulo;
if((b&1)==0)
return (temp*temp)%modulo;
else
return (((temp*temp)%modulo)*a)%modulo;
}
public static long powerwithoutmod(long a, long b)
{
if(b==0) return 1;
long temp=power(a,b/2);
if((b&1)==0)
return (temp*temp);
else
return ((temp*temp)*a);
}
public static double log2(long a)
{ double d=Math.log(a)/Math.log(2);
return d;
}
public static int log10(long a)
{ double d=Math.log(a)/Math.log(10);
return (int)d;
}
public static long gcd(long a, long b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}
public static void tree(int s,int e,int ar[],int c)
{
if(s<=e)
{
int max=s;
for(int i=s;i<=e;i++)
if(ar[i]>ar[max])
max=i;
ar[max]=c++;
tree(s,max-1,ar,c);
tree(max+1,e,ar,c);
}
}
static int resturant=0;
static void DFS(ArrayList<ArrayList<Integer>> al,boolean visited[],int s,int max,int curr,int ar[])
{
visited[s]=true;
if(al.get(s).size()==1&&visited[al.get(s).get(0)]==true)
{resturant++;return;}
// System.out.println(s+" "+curr);
for(int x:al.get(s))
{
if(visited[x]==false)
{
if(ar[x]==0)
DFS(al, visited, x, max, 0, ar);
else if(curr+ar[x]<=max)
DFS(al, visited, x, max, curr+ar[x], ar);
}
}
}
static int solve(long a,long b)
{
if(b==1)
return 1;
long gcd=gcd(a, b);
if(gcd==1)
return -1;
return solve(a,b/gcd);
}
public static void main(String[] args) throws Exception
{
FastIO sc = new FastIO();
//sc.println();
//xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx CODE xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
int test=sc.nextInt();
// // double c=Math.log(10);
// boolean prime[]=new boolean[233334];
// sieve(233334, prime);
// HashMap<Character,Integer> hm=new HashMap<>(9);
// char c='1';
// for(int i=1;i<=9;i++)
// hm.put(c++,i);
while(test-->0)
{
long a=sc.nextLong();
long b=sc.nextLong();
if(b==1)
{
sc.println("YES");
continue;
}
int res=solve(a,b);
if(res==1)
sc.println("YES");
else
sc.println("NO");
}
// xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx CODE xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
sc.close();
}
}
class pair implements Comparable<pair>{
int a;
int b;
pair(int a,int b)
{this.a=a;
this.b=b;
}
public int compareTo(pair p)
{
return (this.b-p.b);
}
}
class triplet implements Comparable<triplet>{
int first,second,third;
triplet(int first,int second,int third)
{this.first=first;
this.second=second;
this.third=third;
}
public int compareTo(triplet p)
{ if(this.third-p.third==0)
return this.first-p.first;
else
return -this.third+p.third;
}
}
// class triplet
// {
// int x1,x2,i;
// triplet(int a,int b,int c)
// {x1=a;x2=b;i=c;}
// }
class FastIO extends PrintWriter {
private InputStream stream;
private byte[] buf = new byte[1<<16];
private int curChar, numChars;
// standard input
public FastIO() { this(System.in,System.out); }
public FastIO(InputStream i, OutputStream o) {
super(o);
stream = i;
}
// file input
public FastIO(String i, String o) throws IOException {
super(new FileWriter(o));
stream = new FileInputStream(i);
}
// throws InputMismatchException() if previously detected end of file
private int nextByte() {
if (numChars == -1) throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars == -1) return -1; // end of file
}
return buf[curChar++];
}
public String nextLine() {
int c; do { c = nextByte(); } while (c <= '\n');
StringBuilder res = new StringBuilder();
do { res.appendCodePoint(c); c = nextByte(); } while (c > '\n');
return res.toString();
}
public String next() {
int c; do { c = nextByte(); } while (c <= ' ');
StringBuilder res = new StringBuilder();
do { res.appendCodePoint(c); c = nextByte(); } while (c > ' ');
return res.toString();
}
public int nextInt() {
int c; do { c = nextByte(); } while (c <= ' ');
int sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
int res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res = 10*res+c-'0';
c = nextByte();
} while (c > ' ');
return res * sgn;
}
public long nextLong() {
int c; do { c = nextByte(); } while (c <= ' ');
long sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res = 10*res+c-'0';
c = nextByte();
} while (c > ' ');
return res * sgn;
}
public double nextDouble() { return Double.parseDouble(next()); }
}
Prime Factor Division CodeChef Solution in PYPY 3
def gcd(m, n):
if m%n==0:
return n
return gcd(n, m%n)
for i in range(int(input())):
a, b = map(int, input().split())
ans = "YES"
while True:
m = gcd(a, b)
if m==b:
break
elif m==1:
ans = "NO"
break
b = b//m
print(ans)Prime Factor Division CodeChef Solution in GO
package main
import (
"bufio"
"bytes"
"fmt"
"os"
)
func main() {
reader := bufio.NewReader(os.Stdin)
var buf bytes.Buffer
tc := readNum(reader)
for tc > 0 {
tc--
s, _ := reader.ReadBytes('\n')
var A, B uint64
pos := readUint64(s, 0, &A)
readUint64(s, pos+1, &B)
res := solve(int64(A), int64(B))
if res {
buf.WriteString("YES\n")
} else {
buf.WriteString("NO\n")
}
}
fmt.Print(buf.String())
}
func readUint64(bytes []byte, from int, val *uint64) int {
i := from
var tmp uint64
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + uint64(bytes[i]-'0')
i++
}
*val = tmp
return i
}
func readInt(bytes []byte, from int, val *int) int {
i := from
sign := 1
if bytes[i] == '-' {
sign = -1
i++
}
tmp := 0
for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
tmp = tmp*10 + int(bytes[i]-'0')
i++
}
*val = tmp * sign
return i
}
func readString(reader *bufio.Reader) string {
s, _ := reader.ReadString('\n')
for i := 0; i < len(s); i++ {
if s[i] == '\n' || s[i] == '\r' {
return s[:i]
}
}
return s
}
func readNum(reader *bufio.Reader) (a int) {
bs, _ := reader.ReadBytes('\n')
readInt(bs, 0, &a)
return
}
func readTwoNums(reader *bufio.Reader) (a int, b int) {
res := readNNums(reader, 2)
a, b = res[0], res[1]
return
}
func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
res := readNNums(reader, 3)
a, b, c = res[0], res[1], res[2]
return
}
func readNNums(reader *bufio.Reader, n int) []int {
res := make([]int, n)
x := 0
bs, _ := reader.ReadBytes('\n')
for i := 0; i < n; i++ {
for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
x++
}
x = readInt(bs, x, &res[i])
}
return res
}
func solve(A, B int64) bool {
if A%B == 0 {
return true
}
g := gcd(A, B)
// S(g) == S(B)
x := B / g
for x > 1 {
if g%x == 0 {
return true
}
y := gcd(g, x)
if y == 1 {
break
}
x /= y
}
return false
}
func gcd(a, b int64) int64 {
for b > 0 {
a, b = b, a%b
}
return a
}Prime Factor Division CodeChef Solution Review:
In our experience, we suggest you solve this Prime Factor Division CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Prime Factor Division CodeChef Solution.
Conclusion:
I hope this Prime Factor Division CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
