DIVBYK - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: satyam_343
Testers: IceKnight1093, tejas10p
Editorialist: IceKnight1093

DIFFICULTY:

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')
2

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;

    }
3

What is mod? I’m assuming it isn’t K.

4

hmm its 1e9+7

5

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
6

ohh ok thanks :heart: