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:
$x = c_0 \times 10^0 + c_1 \times 10^1 \dots c_{len} \times 10^{len}$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:
$N \equiv 0\ (mod\ K)$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.