PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Practice
Setter: Divyam Singal
Tester: Felipe Mota
Editorialist: Aman Dwivedi
DIFFICULTY
Easy
PREREQUISITES
Observation
PROBLEM:
Chef and Divyam are playing a game. They start with a rational number X, such that 0<X<1.
In each turn, Chef chooses a positive real number Y. Then Divyam either adds or subtracts Y to X. So X is replaced with either X+Y or X−Y. If this number becomes 0 or 1, then Chef wins. Otherwise, the game continues.
You are given X, and you have to determine whether Chef can win in a finite number of moves. More formally, does there exist a finite number N so that Chef has a strategy that is guaranteed to win in at most N moves?
Here, X will be given in the form \frac{A}{B}, where A and B are positive integers, A<B and gcd(A,B)=1.
HINT
Spoiler
Chef will win only and only if the denominator B can be expressed in the form of 2^X.
EXPLANATION:
As we know Divyam can either adds or subtracts Y to X. If Chef wants to win in only one move then the result of X-Y should be 0 and the result of X+Y should be 1, then only Chef could win. In all other cases, Divyam is able to perform the operation which doesn’t result in 0 or 1.
Let us find the value of X:
Solving these two equations we get:
Hence our ultimate goal is to make X=\frac{1}{2}. Let us see when we will be able to achieve this value.
Let us represent the given denominator B in prime factorization format. Then there will be two cases possible:
Case 1: There exists some prime number p greater than 2 which is a factor of B
As our ultimate goal is to reduce the denominator to 2. Let us see if we would be able to make the denominator equal to 2. Since A and B are coprime to each other it means that p is not a factor of A
But we would be only able to vanish this p from the denominator only and only when the numerator becomes divisible by p. Hence the goal of Divyam would be to never make the numerator divisible by p while Chef goal is opposite to that of Divyam.
Let us see what happens when Chef gives Divyam a number Y. Let us represent this number Y in the form \Large\frac{A_1}{B}
Why Denominator is B
Although we can use any value in the denominator other than B. But the most optimal choice for Chef is to choose such a number Y whose denominator is the same as that of number X. Because choosing value other than B would unnecessarily increase the prime factors of denominator while we are looking to vanish those prime factors;
Now suppose Chef chooses a number \Large\frac{A_1}{B} and gives it to Chef such that A-A_1 is divisible by X. It means that:
That means:
Let us see what happens if Divyam decides to add Y, then whether (A+A_1) is divisible by p or not. The new numerator will be:
Substituting the value of A_1 mod p from equation (i), we get:
The maximum value that A mod p can achieve is p-1 and the minimum value that it can get is 1. Hence we can rewrite it as:
Since there exists no number which is even and less than p and is divisible by p. It means that Divyam had a choice to perform addition when (A-A_1) is divisible by p.
Similarly, we can prove that when (A+A_1) is divisible by p, then Divyam has a choice to perform subtraction.
Therefore, in this case, we won’t be able to reduce the denominator to 2 and hence Chef won’t be able to win.
Case 2: The only prime number that divides the denominator is 2
Let us see the same thing here too. Suppose Chef chooses a number \Large\frac{A_1}{2} and gives it to Chef such that A-A_1 is divisible by 2. Then using the above proof we can say that:
Let us again see what happens if Divyam decides to add Y, then whether (A+A_1) is divisible by 2 or not. The new numerator will be:
Substituting the value of A_1 mod 2 from equation (ii), we get:
The only possible value of A mod 2 is 1. When we multiply A mod p by 2 we get 2 and hence that is divisible by 2. Hence Divyam has no choice left to prevent the denominator from getting divisible by 2. Hence after a finite number of moves, we would be able to reduce the denominator to 2.
Therefore Chef will win in this case.
TIME COMPLEXITY:
O(log2(N)) per test case
SOLUTIONS:
Setter
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define vll vector<ll>
#define ld long double
#define pll pair<ll,ll>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define oset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define osetll tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ook order_of_key
#define fbo find_by_order
const int MOD=1000000007; //998244353;
long long int inverse(long long int i){
if(i==1) return 1;
return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
if(b==0) return 1;
if(b==1) return a%MOD;
ll temp=POW(a,b/2);
if(b%2==0) return (temp*temp)%MOD;
else return (((temp*temp)%MOD)*a)%MOD;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
ll t;
cin>>t;
for(int i=0;i<t;i++)
{
ll a,b;
cin>>a>>b;
ll flag=0;
for(int i=1;i<60;i++)
{
if(b==(1ll<<i))
{
flag=1;
break;
}
}
if(flag==1) cout<<"Yes";
else cout<<"No";
cout<<"\n";
}
}
Tester
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
long long v;
cin >> v;
return v;
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
long long TEN(int p){ long long r = 1; while(p--) r *= 10; return r; }
long long gcd(long long a, long long b){
while(b) a %= b, swap(a, b);
return a;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t = readIntLn(1, TEN(6));
while(t--){
long long a = readIntSp(1, TEN(18));
long long b = readIntLn(1, TEN(18));
assert(a < b && gcd(a, b) == 1);
while(b % 2 == 0) b /= 2;
cout << (b == 1 ? "Yes\n" : "No\n");
}
return 0;
}
Editorialsit
#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
int a,b;
cin>>a>>b;
while(b%2==0)
b/=2;
if(b==1)
cout<<"Yes"<<"\n";
else
cout<<"NO"<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin>>t;
while(t--)
solve();
return 0;
}
