# DIVBYK - Editorial

Author: satyam_343
Testers: IceKnight1093, tejas10p
Editorialist: IceKnight1093

1329

# PREREQUISITES:

Basic modular arithmetic

# PROBLEM:

Given an array A, find a subset whose product is divisible by K or report that none exist.

# EXPLANATION:

Suppose that we had a subset S whose product was divisible by K.
Then, notice that if we add more elements to the subset, its product will still be divisible by K.

So, itâ€™s enough to check whether the product of all the elements is divisible by K.

However, the product of all elements is too large to compute (at least in C/C++).
Instead, notice that we only care about whether the product is divisible by K or not, not what the actual product is.

So, we can just compute A_1\cdot A_2 \cdot \ldots \cdot A_N \pmod K and check whether this is zero or not.
Computing this can be done with a loop as follows:

• Initialize a variable prod = 1.
• For each i from 1 to N, do the following:
• Multiply prod with A_i modulo K, i.e, set prod \to (prod \cdot A_i) \pmod K
• The final value of prod is what we want. Check whether itâ€™s zero or not, and weâ€™re done.

# TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

# CODE:

Code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
prod = 1
for x in a:
prod *= x
prod %= k
print('Yes' if prod == 0 else 'No')


canâ€™t we use mod each time like this?? it gave WA

for(int i=0; i<n; i++){

        if(a[i]%k==0) flag = 1;

prod = (prod * a[i]) % mod;

prod = prod %mod;

}

What is mod? Iâ€™m assuming it isnâ€™t K.

hmm its 1e9+7

That obviously wonâ€™t work, right?

For example, if A = [2, 5\times 10^8 + 4] and K = 2, youâ€™d compute the product of the array to be 10^9 + 8 which is 1 modulo your mod and so youâ€™d answer â€śNoâ€ť, but in reality the product is even so the answer should be â€śYesâ€ť

In general mixing multiple mods isnâ€™t going to end well unless you have some special conditions (for example, if one mod divides the other then youâ€™re somewhat ok in certain cases, which is what the Chinese Remainder Theorem uses).

1 Like

ohh ok thanks