PROBLEM LINK:Setter Misha Chorniy DIFFICULTY:CAKEWALK/SIMPLE PREREQUISITES:Modulo Operator (%), Basic Maths of Addition, Logic PROBLEM:Let me denote knowledge by $A$ and power by $B$. Now, as given in the question, we initially have $A=1$ and $B=1$. Tell if its possible for you to reach $A=N$ AND $B=M$ using following operations
QUICKEXPLANATION:Key to AC Modulo along with careful checking for corner case ($N=1$ or $M=1$) fetched AC in first try. The problem clearly asks if you can find two integers $k$ and $l$ such that either ($1+X*k=N$ $\&\&$ $1+Y*l=M$) OR ($1+X*k=N1$ $\&\&$ $1+Y*l=M1$). Move the $1$ in $LHS$ to $RHS$ to get equations in form ($X*k=N1$ $\&\&$ $Y*l=M1$) OR ($X*k=N2$ $\&\&$ $Y*l=M2$). Lets consider one equation for example, say $X*k=N1$. Clearly, $LHS$ can move only in steps of X. This means, $X*k$ can never be equal to $N1$ (for all possible integers $k$) if $N1$ is not a multiple of $X$, or in other words, if $N1$ is not divisible by $X$. Similar analogy holds in other $3$ equations. EXPLANATION:The problem is quite simple, hence we will have only a single section in editorial. We will discuss editorialist's solution in those. I might sound overexplanative in the explanation below, and perhaps you may ask "Why is he now considering case only for Knowledge and not considering Power right now?" &etc. I want you, the reader, to patiently read it. I have tried to picture the thought process which should be on your mind when typically solving such easy problems, so please try to grasp it if possible. :) Editorialist's Solution For sake of formality, lets discuss the first subtask's solution first. We can brute force for task $1$. The idea is, keep increasing Knowledge by $X$ as long as its less than $N$, and keep increasing power by $Y$ as long as its less than $M$. At last, check if Knowledge$==N \&\&$ Power$==M$. If not, subtract $X$ from Knowledge and $Y$ from Power and check Knowledge$==N1 \&\&$ Power$==M1$. The above fails, or gets time limit exceeded, if number of steps for Knowledge and Power to reach $N$ and $M$ are large. For the full solution, first ask yourself what exactly do we have to check? Let me denote knowledge by $A$ and power by $B$. Now, we initially start with $A=1$, $B=1$ and have to see if we can reach $A=N$, $B=M$. At each step, we can add $X$ to $A$, $Y$ to $B$, or use the special operation $1$ to both $A$ and $B$ . The special operation can be done only once. Think on the special operation. It increases $A$ and $B$ by $1$. When will it exactly be useful to us? It can help us reach $A=N$ and $B=M$ if, and only if we can reach $A=N1$ and $B=M1$ first. If we reach there, then we can use this special operation to reach $A=N$ and $B=M$ (Recall that it will increase $A$ and $B$ both by $1$). Now the problem reduces to, checking if we can reach ($A=N$ $\&\&$ $B=M$) OR ($A=N1$ $\&\&$ $B=M1$) by moving in steps of $X$ (for $A$) and $Y$ (for $B$). Lets talk about $A$ for now, the exact same thing will be later applied to $B$. We initially have $A=1$, we can increase it in steps of $X$ in normal operations. Say, I apply the operation $k$ times, then my $A$ will be  $A=1+X*k$ Forget about everything else now. Just see that we have $A=1+X*k$, and we have to reach an integer $N$. When will it be possible? We see that we need $1+X*k=N$ $\implies X*k=N1$ Stop there. See the $LHS$, i.e. $X*k$. $k$ must be an integer, as number of operations is a whole number. Hence, this means $LHS$ will always be a multiple of $X$. Also, since $k$ can be any whole number, we can see that, $LHS$ can reach any multiple of $X$. But can we reach numbers which are not multiples of $X?$ No! Because if we could, then it will contradict the fact that $k$ is a whole number (and not a fraction r decimal). This means, all we need to check is to see if $N1$ is a multiple of $X$ or not! If it is, we can reach it, if its not, then we cannot reach it. And since we used no special property (i.e. no property which was only available only to $A$ and is not available to $B$), we can repeat the above steps and arrive at $Y*l=M1$, where $l$ is number of times operation is done. Then, using arguments above, we conclude we can reach $M$ iff and only if $M1$ is divisible by $Y$! Now lets bring the special operation into the picture. So far, we know how to check if we can reach a given number $N$ or $M$ from $A=1$ and $B=1$. What change does the special operation bring? See above, it just has the effect of "If I can reach $N1$ and $M1$, I can then use special operation to reach $N$ and $M$" Hence, our conditions reduce to checking
The main aim of this editorial was not to merely explain solution of the problem, but to plant the thoughtprocess which should go on your mind, as these are the common techniques, methods and tricks which will ultimately help you ace out as a programmer. On a side note, beware of the corner case $N=1$ or $M=1$. We can prove that special operation cannot be used if $N=1$ or $M=1$. (Proof in bonus section.) Try to frame the conditions in your coding language now. An implementation in C++ is given below for reference :). SOLUTIONThe respective codes are also pasted in tabs below in case the links do not work. This is for convenience of readers, so that they can copy paste it to whichever IDE or editor they are comfortable reading it in and immediately have access to the codes. :) Setter $Time$ $Complexity=O(1)$ per test case CHEF VIJJU'S CORNER :D1. Proof that we cannot apply special operation of ShareChat if $N=1$ or $M=1$. 2. Solve the below $2$ questions based on variants of  "Say, instead of special operation increasing $A$ and $B$ by $1$, it did following" 3. A LOT of you guys made a silly error which got you WA in both the subtasks. It is generally known that $(ab)\%m=a\%m b\%m$ if $b\le a$. And we can also write it as $(ab)\%m=a\%m b\%m=a\%m b$ if $b<m$ and $b<a\%m$ . So lot of you guys did $(N1)\% X ==0\implies N\% X==1$ and similarly for $M$ and $Y$. Ask yourself, is this step correct? Well, it is for $998$ out of $1000$ inputs, but at cases where $X=1$ and/or $Y=1$, this fails miserably, because that case $b \% m= 1 \% 1=0$!! Be very, very careful when doing such manipulations under modulo, and always check if they are allowed or not! 4. Related Problems asked 07 Sep '18, 01:17

Just for fun, a Python implementation making use of True == 1 and False = 0:
And it was very kind of the setter to give a public test case in which the use of the "install" option was not viable. :) answered 19 Sep '18, 02:46

@krishyayadav007 check for input 4 3 2 1 for this the answer should be Chefirnemo answered 19 Sep '18, 10:32

Can I know on which testcase my code fails ?. Here is my soloution. I got correct output for subtask#2 but got wrong answer for subtask#1. answered 19 Sep '18, 11:40
