# PROBLEM LINK:

Practice

Div-3 Contest

Div-2 Contest

Div-1 Contest

* Author:* Divyam Singal

*Felipe Mota and Radoslav Dimitrov*

**Testers:***Divyam Singal*

**Editorialist:**# DIFFICULTY:

Easy-Medium

# PREREQUISITES:

Game Theory, Number Theory

# PROBLEM:

Chef and Divyam are playing a game with the following rules:

- First, an integer X! is written on a board.
- Chef and Divyam alternate turns; Chef plays first.
- In each move, the current player should choose a positive integer D which is divisible by up to Y distinct primes and does not exceed the integer currently written on the board. Note that 1 is not a prime.
- D is then subtracted from the integer on the board, i.e. if the integer written on the board before this move was A, it is erased and replaced by A−D.
- When one player writes 0 on the board, the game ends and this player wins.

Given X and Y, determine the winner of the game.

# QUICK EXPLANATION:

Let A denote the product of first (Y+1) primes. Then the first player wins if X! is not divisible by A, else second player wins.

Let the number on the board currently be N. This game can be considered as having two states, one in which N is divisible by A, call it the **divisible** state and other where N is not divisible by A, call it the **not divisible** state.

We can’t go from a **divisible** state to a **divisible** state after a move as it would mean the number which has been subtracted should also be a multiple of A which is not possible.

And we can go from a **non divisible** state to a **divisible** state, by removing the remainder of dividing N by A.

So if X! is not divisible by A, the first player can always play to ensure he gets a **non divisible** number each time, to which he converts it into a **divisible** number for the second player. As 0 is a **divisible** state, the first player would win. Similar strategy works for second player in the case X! is divisible by A.

# EXPLANATION:

We introduce a variable A, which is the product of the first (Y+1) primes.

Let us get some intuition as to why we have chosen such a number A.

**Lemma 1:** The difference between two multiples of A will have at least Y+1 distinct prime factors.

## Proof of Lemma 1

Let the first Y+1 prime factors be P_1,P_2, \dots ,P_{Y+1} and let the two multiples of A be a_1 and a_2

We can write a_1 and a_2 as-

a_1=K_1P_1P_2\dots P_{Y+1}

a_2=K_2P_1P_2\dots P_{Y+1}

where k_1 and k_2 are some positive integers.

Then a_1-a_2=(K_1-K_2)P_1P_2\dots P_{Y+1}, and hence it has at least Y+1 distinct prime factors P_1,P_2, \dots ,P_{Y+1}.

**Lemma 2:** The remainder after dividing a non-multiple of A by A will have at most Y distinct prime factors.

## Proof of Lemma 2

Let a non-multiple of A be a.

By the Euclid’s Division lemma, we can write a=bA+r, where 0 \le r < A.

For the sake of contradiction, let us assume that the remainder r is divisible by at least Y+1 primes.

The product of at least Y+1 distinct primes will be more than A, as A is the product of the first Y+1 primes. This will lead to contradiction due to the fact that r<A.

We now define the two states of the game. Let the number on the board currently be N.

The state is called **divisible** if N is divisible by A and the state is called **non-divisible** if N is not divisible by A.

Let us think about the transitions in these two states. Here transition means a change in state after a player’s move.

**Lemma 3:** From a **divisible** state, we are forced to go to a **non-divisible** state.

## Proof of Lemma 3

For the sake of contradiction, let us assume that we can go from a **divisible** to a **divisible** state. Using Lemma 1, we know that the difference between them have at least Y+1 prime factors, which is not possible as a move consists of subtracting a number having at most Y prime factors.

So from a **divisible** state, we can only (forcefully) go to a **non-divisible** state.

**Lemma 4**: From a **non-divisible** state, we can go to a **divisible** state.

## Proof of Lemma 4

From Lemma 2, we know that the remainder after dividing a non-multiple by A will have at most Y distinct prime factors. Subtracting the remainder of dividing N by A will be a valid move as it will have at most Y distinct prime factors. The number after subtracting the remainder will be a multiple of A.

Now in our game, having a **non-divisible** state is a winning state. This is because 0 is a divisible state, so the player having a **non-divisible** state can only arrive to 0.

Using Lemmas 3 and 4, we observe that a player can maintain the **non-divisible** state. This is because from a **non-divisible** state, the other player will get a **divisible** state. And from the **divisible** state, the player is helpless, leaving a **non-divisible** state for this initial player.

So Chef i.e. the first player will win the game if he starts with the **non-divisible** state, otherwise Divyam i.e. the second player will win the game.

Our problem reduces to just checking whether X! is divisible by the product of first Y+1 primes or not.

To check this, we will first find all the prime numbers from 1 to 10^6. This can be done by using the Sieve approach.

## Sieve method

```
for(int i=0;i<1000001;i++)
{
prime[i]=1; //initially every number is marked as prime
}
for(int i=2;i*i<=1000000;i++)
{
if(prime[i]==1)
{
//marking multiples of i as non-prime
for(int j=2*i;j<=1000000;j+=i)
{
prime[j]=0;
}
}
}
//Time complexity is O(nlogn)
```

Next we will find the prefix sum of the primes, which stores the count of primes not greater than it.

This is the pre-build work, which can be done in O(XlogX).

Then for each test case, all we do is compare the pref\_sum[X], which we calculated above with Y+1. If it is smaller, Chef (first player) wins and otherwise Divyam (second player) wins.

So each test case takes O(1) time.

The total time complexity is O(XlogX+T).

# SOLUTIONS:

## Setter's Solution

```
#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 prime[1000001],pre[1000001];
for(int i=0;i<1000001;i++)
{
prime[i]=1;
}
for(int i=2;i*i<=1000000;i++)
{
if(prime[i]==1)
{
for(int j=2*i;j<=1000000;j+=i)
{
prime[j]=0;
}
}
}
pre[0]=0;
pre[1]=0;
for(int i=2;i<=1000000;i++)
{
pre[i]=pre[i-1]+prime[i];
}
ll t;
cin>>t;
for(int i=0;i<t;i++)
{
ll x,y;
cin>>x>>y;
if(pre[x]<y+1) cout<<"Chef";
else cout<<"Divyam";
cout<<"\n";
}
}
```

## Tester's Solution

```
#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 a;
cin >> a;
return a;
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,' ');
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
const int maxy = 20000000;
vector<int> factor(maxy + 1, -1), primes;
for(int i = 2; i <= maxy; i++){
if(factor[i] == -1){
primes.push_back(i);
for(int j = i; j <= maxy; j += i){
if(factor[j] == -1)
factor[j] = i;
}
}
}
int t = readIntLn(1, 1000000);
while(t--){
int x, y;
x = readIntSp(1, 1000000);
y = readIntLn(1, 1000000);
if(x >= primes[y]) cout << "Divyam\n";
else cout << "Chef\n";
}
return 0;
}
```