SATA01 - Editorial

PROBLEM LINK:

Practice

Contest

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.

//