acm.sgu Magic Pairs

Radim redom zadatke sa Saratova..
I naidjoh na neke matematicke..I odmah da vas pitam kako se rade :)
Mislim, ne volim takve zadatke gde se buta cista matematika, ali ipak
od viska glava ne boli , a mozda ih i zavolim :)
linkovi su:

http://acm.sgu.ru/problem.php?contest=0&problem=118
http://acm.sgu.ru/problem.php?contest=0&problem=119

ovaj prvi je uradila gomila ljudi, ali ja nemam neko lepo resenje koje bi proslo za 0.25 sekudi na
nekom krsu koji oni koriste za server.

Unapred zahvalan,
Relja

edit : dodao sam 118

Digital root od X ti je 9 ako je X djeljiv s 9, a inace je ( X % 9 )
Kad to znas mozes napraivit ful lako O( n ) algoritam

Hvala momche :)

np :)

Za drugi ti je hint ovaj dokaz:

5x + 4y = 0 ( mod 23 )
<=>
- 5x - 4y = 0 ( mod 23 )
<=>
23( x + y ) - 5x - 4y = 0 ( mod 23 )
tj.
18x + 19y = 0 ( mod 23 )
<=>
18x + 19y - 3*( 5x+4y ) = 0 ( mod 23 )
tj.
3x + 7y = 0 ( mod 23 )

gl :)

Videcu da li sam dovoljno dobar da nastavim :)
Hvala.