Fișierul intrare/ieșire rest.in, rest.out Sursă Olimpiada locala 2014, Clasa a 5-a
Autor autor necunoscut Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 1 sec Limită de memorie 1024 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Rest (clasa a 5-a)

Andrei, mare pasionat de matematică, compune adesea probleme cu numere mari: fie N un număr natural care poate avea maxim 100 000 de cifre în scrierea în baza 10, pe un astfel de număr se definește prefix al lui N ca fiind un număr format din primele cifre ale lui N, în ordine de la stânga la dreapta. Prefixul poate avea minim o cifră și maxim tot atâtea cifre ca N. Restul modulo K al unui număr natural este restul obținut la împărțirea întreagă a acelui număr la K.

Cerință

Ajutați-l pe Andrei sa rezolve următoarea problemă: considerând resturile modulo K ale tuturor prefixelor lui N, determinați care este restul maxim care apare și pentru câte dintre aceste prefixe se obține.

Date de intrare

Fișierul de intrare rest.in conține pe prima linie numărul natural K, iar pe a doua linie un șir de cifre, despărțite printr-un spațiu, reprezentând cifrele numărului natural N.

Date de ieșire

Fișierul de ieșire rest.out va conține pe prima linie două numere naturale r nr, despărțite printr-un spațiu, reprezentând restul maxim modulo K determinat și numărul de prefixe pentru care se obține acest rest.

Restricții

  • 1 ≤ K ≤ 100
  • 1 ≤ numărul de cifre ale lui N ≤ 100 000

Exemplu

rest.in rest.out Explicație
3
2 4 5 3
2 3
Prefixele ce se pot obține sunt: 2, 24, 245 și 2453,
iar resturile modulo 3 sunt în ordine: 2, 0, 2, 2

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii