Given an array a and an integer k, in each step, you can choose 2 indices i and j and change a_i to a_i+a_j. Can you make all the elements divisible by k?
QUICK EXPLANATION:
Let k=o*2^p where o is odd. The answer is yes if and only if o divides every element of a.
EXPLANATION:
First, let’s look at what happens when i=j. You simply multiply your element by 2. If you keep repeating that, you can multiply it by any power of 2 you want. So that means if k is a power of 2 for example, the answer is always yes, because you can make all the elements divisible by as large powers of 2 as you want.
Let’s try to generalize this. Notice that you can always split k as the product of 2 factors: a power of 2, and an odd part. So let’s write k=o*2^p. It’s enough to make all the elements of a divisible by o. Then, you can just keep multiplying them by 2 to make them divisible by k as well. So now we just want to make them all divisible by o. If they already are, the answer is clearly yes. Otherwise what happens?
Let’s say you keep doing the operation until there’s one and only one element which isn’t divisible by o. Now, no matter what you do, you can’t make this element divisible by o (without breaking what you did for the other elements.) That’s because every other element in the array is a multiple of o, so adding any of them to it won’t change its remainder when divided by o. Also, multiplying it by 2 won’t help since o is odd. So it seems like the answer is always no in this case, making the answer yes if and only if all the elements are already divisible by o.
SOLUTIONS:
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
scanf("%d",&t);
while (t--)
{
int n,k;
scanf("%d%d",&n,&k);
while (k%2==0)
k/=2; //keep only the odd part of k, which we called o
bool ok=1;
for (int i=0;i<n;i++)
{
int a;
scanf("%d",&a);
ok&=(a%k==0);
}
puts(ok? "YES":"NO");
}
}
Thanks for the great explanation! I mostly understand it.
I am having a hard time understanding the proof of why just checking divisibility with o is enough.
“we just want to make them all divisible by o”
I am interpreting this to mean three things:
If every element is divisible by o, then we can make every element divisible by k.
I get this.
If an element is not divisible by o, then we can try to make it divisible by other elements who are not divisible by o, but at last we will be left with 1 element. So overall this will not lead to a solution.
I get this.
If an element is not divisible by o, then we can’t make it divisible by other elements who ARE divisible by o.
I don’t get this part. Why can’t a non-divisible-by-o element use a divisible-by-o element to become divisible? Note that, divisible-by-o elements might not be divisible by k (until you multiply by 2). So it’s totally possible to generate non-zero remainders from them that can be used by other elements. What am I missing?
Claim:non-divisble-by-o elements can’t be made divisible by k by using divisible-by-o elements.
Proof: Let’s say we have two elements d and e, where d is divisible by o, but e is not. So d can be written as d=c1*o, where c1 is some integer.
Now let’s say we want to make e divisible by k. But before that, let’s try to make e divisible by o first, and we will worry about divisibility with k later. Note that anything that is divisible by k is also divisible by o. So our updated e has to be divisible by o to have any chance of being divisible by k. So, let’s focus on o first.
To make e divisible by o, let’s try to use d.
We are looking for a constant c2, such that e_dash = e + c2*d is divisible by o. Let’s see what the remainder looks like for e_dash. e_dash % o
= (e + c2*d)%o = (e + c2 *c1*o)%o // (remember from above d=c1*o) = (e%o) + (c2*c1*o)%o = (e%o) + 0 = e%o
So basically we couldn’t change the remainder. Even after adding any multiple of d, the remainder doesn’t change because multiples of d are all divisible by o.
So, if we can’t make e divisible by o, then we have no chance of making it divisible by k, because k is a multiple of o.
Hence proved that non-divisible-by-o elements (like e) can’t be made divisible by k by using divisble-by-o elements (like d).