algorithm - Finding the mutiples in form of 0 and 1 -

i trying solve http://poj.org/problem?id=1426 (2002 dhaka regional) . though not able come exact algorithm required n varied 1 200 precomputed values generating binary numbers , checking divisibility.now have constant time algorithm :) sure not correct approach problem. dont want use graph search algos problem under basic math in site think there must mathematical solution problem not give tle. if suggest way of doing right way grateful.

it's simple trick on remainder.

having write every multiple 0 , 1, means want multiple sum of powers of 10, means x=\sum{10^a(i)} {a(i)}. find proper index want keep, must remember that, being multiple of number n means x mon n = 0.

so, it's writing powers of 10 mod n, , find subset sum 0 mod n. let's try 19:

num -> num mod 19 1 -> 1 10 -> 10 10^2 -> 5 10^3 -> 12 10^4 -> 6 10^5 -> 3 

now, can see 10^1 + 10^4 + 10^5 = 19 0 mod 19, our solution 110010 . find reminder mod 19 don't have calculate every single power, can multiply previous value mod 19 per 10, , calculate module.

for instance, 10^4 mod 10 = 10^3 * 10 mod 19 = 12*10 mod 19 = 6 , way easier calculate 10^4 ( maybe it's not small powers, imagine having calculato 100^100 before making mod 19).

edit

the problem left find subset sums 0 mod n, assuming such subset exist.

edit

ok, have got idea works n = 200 , solve problem on linear time. basically, exploit fact sums mod n sooner or later overlap. true because of hte pigeot principle, in specific case, having 100 integers, having working mere case. anyway, given list of reminders calculated shown before, start calculatin partial sums. if meet value had, have solution ( i-1 1's followd j 0) . if meet reminder 0, done.

here c# code i've written test it:

        (int n = 2; n <= 200; n++)         {             int[] reminder = new int[100];             reminder[0] = 1;             (int = 1; < 100; i++)             {                 reminder[i] = (10 * reminder[i - 1]) % n;              }             var lst = reminder.select((x, y) => new tenpower { reminder = x, pow = y })                 .tolist();              bool cont = true;             (int = 1; (i < 100)&&cont; i++)             {                 if (lst[i].reminder == 0)                 {                     cont = false;                     console.writeline(n +" :: " + math.pow(10, lst[i].pow));                 }                 else                 {                     lst[i].reminder = (lst[i].reminder + lst[i - 1].reminder) % n;                     if (lst[i].reminder == 0)                     {                         cont = false;                         console.writeline(n + " :: " + math.pow(10, lst[i].pow));                     }                     (int j = - 1; (j > 0) && cont; j--)                     {                         if (lst[i].reminder == lst[j].reminder)                         {                             cont = false;                             console.write(n + " :: ");                             (int k = 0; k < - j; k++)                             {                                 console.write("1");                             }                             (int k = - j-1; k < i; k++)                             {                                 console.write("0");                             }                             console.writeline();                         }                     }                 }             }         }