PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Vishesh Saraswat
Testers: Nishank Suresh, Satyam
Editorialist: Nishank Suresh
DIFFICULTY:
2016
PREREQUISITES:
Familiarity with prime factorization
PROBLEM:
Given two integers A and B, does every prime dividing B also divide A?
EXPLANATION:
The obvious solution is to attempt to prime-factorize B and then check if each prime factor divides A.
Unfortunately, both the number of test cases and the numbers themselves are too large: even a fast prime-factorization algorithm likely isn’t going to be fast enough, so we need to be a bit smarter.
There’s a couple of different ways to approach this task, though for the most part they rely on looking at the prime factorizations of A and B and drawing some conclusions from that.
Method 1 (GCD)
Consider a prime p that divides B. Suppose it also divides A.
Then, p definitely divides \gcd(A, B).
In particular, since \gcd(A, B) is a factor of B, the answer to the initial question is “Yes” if and only if B and \gcd(A, B) have the same set of primes dividing them.
So, we essentially reduce our problem to this: given two integers x and y, where y is a factor of x, do they have the same set of prime factors dividing them?
- If x = 1, then y = 1 and the answer is obviously “Yes”.
- If x \gt 1 but y = 1, the answer is obviously “No”.
- Otherwise, we have x, y \gt 1. Since y \mid x, let’s look at z = x/y.
- Consider some prime p that divides x.
- If x and y have the same power of p, then z doesn’t contain p at all.
- Otherwise, z does contain some power of p. So, p divides y if and only if p divides \gcd(z, y).
In other words, in the case when x, y \gt 1, they have the same prime factors if and only if z and \gcd(z, y) have the same prime factors!
This gives us a pretty simply algorithm:
- Initially, x = B and y = \gcd(A, B).
- While x \gt 1 and y \gt 1, replace x and y with x/y and \gcd(y, x/y).
- In the end, if x = 1 the answer is “Yes” and otherwise the answer is “No”.
The while loop runs only \mathcal{O}(\log B) times, since at each step the larger number is at least halved. This is fast enough for our purposes.
Method 2 (Exponentiation)
A rather interesting solution is to simply compute A^{60} \bmod B and check whether this is 0 or not.
Computing A^{60} \bmod B can be done quickly with exponentiation, however if you’re using C++ or Java you’ll need to use 128-bit integers or something like this, since otherwise the multiplications will overflow even long long.
Why does this work?
The idea behind this solution is simple: if p is a prime that divides B, then p divides A if and only if p divides A^{60}.
This follows from the fact that the largest power of a prime that fits within 10^{18} is 59 (since 2^{60} \gt 10^{18}).
The prime factorization of A^{60} has every prime to a power of at least 60, which is strictly larger than the power of anything in B. So, every prime in B divides A^{60} if and only if then B itself divides A^{60}, so we simply check that instead.
TIME COMPLEXITY
\mathcal{O}(\log B) per test case.
CODE:
Setter's code (C++)
#include "bits/stdc++.h"
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
*/
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define sz(x) (int)(x).size()
using ll = long long;
#define int ll
const int mod = 1e9+7;
void solve(int tc) {
int a, b;
cin >> a >> b;
int g = gcd(a, b);
int gg = gcd(g, b);
while (b % gg == 0 and gg != 1) {
b /= gg;
gg = gcd(gg, b);
}
cout << (b == 1 ? "YES\n" : "NO\n");
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
int tc = 1;
cin >> tc;
for (int i = 1; i <= tc; ++i) solve(i);
return 0;
}
Tester's code (C++)
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(char x){cerr<<x;}
void _print(string x){cerr<<x;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> 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<<"]";}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;
const ll MAX=1000100;
void solve(){
ll a,b; cin>>a>>b;
ll g=__gcd(a,b);
while(b!=1){
ll x=__gcd(g,b);
if(x==1){
cout<<"NO\n";
return;
}
b/=x;
}
cout<<"YES\n";
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Editorialist's code (Python)
for _ in range(int(input())):
a, b = map(int, input().split())
print('Yes' if pow(a, 60, b) == 0 else 'No')
