Problem statement
Today Anupam and Aman are playing a game called Game of Remainders. Anupam chooses two positive integers, a and b, and tells Aman about b but not a. Aman has to find the value of a mod b. There are ‘n’ ancient numbers c1, c2, ..., cn, and Anupam has to tell Aman the value of ‘a’ mod ‘ci’ (where ci can be any element out of these n integers from c1 to cn).if Aman asks. Given ‘b’ and the ancient values, tell us if Aman has a winning strategy independent of the value of ‘a’ or not. Formally, is it true that Aman can understand the value a mod b for any positive integer a? The first line of the input contains two integers n and b here n depicts the number of ancient integers and value ‘b’ that is chosen by Anupam. Print "Yes" if Anupam has a winning strategy independent of the value of a, or "No" otherwise.
Note, that a mod b means the remainder of a after dividing it by b.
Example 1
Input
4 5
2 3 5 12
Output
Yes
Explanation
In this example, Aman will win the Game of Remainders because Aman can understand because a mod 5 is one of the ancient numbers. Here the value of b is 5 and we have to find a%5 we are also given with 2%5, 3%5, 4%5 and 5%5 and 12%5. So if we assume initially that aman can not find and ans is no then there must exist a pair of integers x1 and x2 such that both of them have the same remainders after dividing it by any ci, but they differ in remainders after dividing by b but we can see this is not the case here hence aman can win. To get a better understanding please see the entire approach given below in the blog.
Example 2
Input
2 7
2 3
Output
No
Explanation
In this example, Aman can't be sure what a mod 7 is. For example, 1 and 7 have the same remainders after dividing by 2 and 3, but they differ in remainders after dividing by 7.
Approach
To solve this problem “Game of Remainders” you should have a great grasp of the number theory concepts. So we can solve this problem using the assumption technique. Initially, assume that the answer is always No. There must exist a pair of integers x1 and x2 such that both of them have the same remainders after dividing it by any ci, but they differ in remainders after dividing by b.
For example let x1 be 3 and x2 be 15 and let c1 is 2 and c2 is 3 so both x1 and x2 give the same remainder on dividing this by c1,c2,..... And so on till cn
Now we can conclude to this:
We have x1 - x2 ≡ 0(mod ci) for every 1 ≤ i ≤ n.
So :
lcm(c1,c2,c3,....cn) is a multiple of x1-x2 and b is not a multiple of lcm(c1,c2,c3,....cn)
Now We've found a necessary condition. And I have to tell you that even this condition is also sufficient! Assume this condition that b is not a multiple of lcm(c1,c2,c3,....cn), we are going to prove there exists x1, x2 such that x1 - x2 ≡ 0 (mod ci) (for each 1 ≤ i ≤ n), and x1 - x2 ≡ 0 (mod b).
A possible solution could be x1 = lcm(c1, c2, ..., cn) and x2 = 2 × lcm(c1, c2, ..., cn), so the sufficiency is also proved.
So you have to only check if lcm(c1, c2, ..., cn) is divisible by b, which could be done using prime factorization of b and ci values.
Below is the implementation for the given approach.
Algorithm
- Iterate on all the ancient number given in the vector
- While iterating calculate the least common factor for all the array elements such that it has a common factor with b
- To find lcm for two numbers use the property that lcm(two numbers)*hcf(two numbers) = product of two numbers
- To find hcf of the number use inbuilt gcd function in c++
Code:
// c++ code for problem Game of Remainders between aman and anupam
#include <bits/stdc++.h>
using namespace std;
int gcd(int x, int y) {
// Inbuilt function to find gcd in c++ function
return __gcd(x, y);
}
int lcm(int x, int y)
{
// function to find the lcm using the formula HCF*LCM = X*Y
return x * y / gcd(x, y);
}
int main() {
// c++ code for problem Game of Remainders
int n = 4;
int b = 5;
vector<int> v_ancient = {2,3,5,12};
int cur = 1;
// Iterating on all the elements
for (int i = 0; i < n; ++i) {
// finding the lcm for all the numbers such that it has a common factor with b
cur = gcd(b, lcm(cur, v_ancient[i]));
}
if (cur == b) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}Output:
YesTime Complexity
O(n * 𝑙𝑜𝑔(max(x, y))
The time complexity to solve this problem Game of Remainders between aman and Anupam is O(n * 𝑙𝑜𝑔(max(x,y)). Where 'n' is the total size of the array containing the values of ancient numbers and x and y are the parameters going in the function of the inbuilt gcd function. It use the Euclidean method to calculate ate gcd of two values. Its complexity is 𝑂(𝑙𝑜𝑔2𝑛) algorithm, where ‘n’ is the upper limit of x and y. We are calculating for every ancient number while doing iteration in the array hence the total time complexity will be O(n * 𝑙𝑜𝑔(max(x,y)).
Space Complexity
O(1)
The space complexity to solve this problem of Game of Remainders between aman and anupam is O(1). Since we haven't used any extra data structure in the entire implementation of the given problem statement the space complexity for this approach is constant.
Also see, Euclid GCD Algorithm
39+ registered 