### PROBLEM LINK:

**Author:** Akul Sareen

**Tester:** Anmol Sood, Tapan Sahni

**Editorialist:** Akul Sareen

### DIFFICULTY:

CAKEWALK

### PREREQUISITES:

Basic Math

### PROBLEM:

Given 2 numbers **N** and **K**, tell if **N** is divisible by **K**.

### QUICK EXPLANATION:

Represent decimal notation of **N** as a polynomial with x = 10. Now evaluate this polynomial mod **K**.

### EXPLANATION:

Take any number, say 132. Now we can represent this number as the sum of powers of 10 multiplied with appropriate coefficients i.e.:

$132 = 1 \times 10^2 + 3 \times 10^1 + 2 \times 10^0$More generally, we can represent any number **x** as:

where len is the length of **x** in decimal notation and c_0,c_1,\dots,c_{len} are all the digits in the decimal notation of **x**.

Also, if **K** divides **N**, then:

At this point you can write a solution that finds all the powers of 10 mod **K** and then adds up all the values of the coefficients times powers of 10 and maintains that mod **K**. If the result is 0 then **N** is divisible by **K**, otherwise it is not.

### ALTERNATIVE SOLUTION:

It is possible to use Horner’s rule to simplify evaluation of **N** mod **K** to a for loop with just one line inside.

You may also use Java or Python and use arbitrary precision arithmetic. You can also achieve the same effect by writing a BigInteger library in other languages without built-in support.

It might also be possible to derive divisibilty rules for all numbers from 1 to 10 and use those to find the answer. **K** was deliberately kept small to allow that possibility.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution will be uploaded later.