Fişierul intrare/ieşire:jap2.in, jap2.outSursăAlgoritmiada 2010, Runda 2
AutorBogdan-Cristian TataroiuAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test3.5 secLimită de memorie22528 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Jap2

Bercea a primit sarcină de la mentorul său să facă o poveste frumoasă pentru următoarea problemă care va fi dată la Algoreea 2010. Înainte de asta, Bercea ar vrea să ştie cum se rezolvă şi vă cere ajutorul în schimbul unui cadou pe Facebook. Problema sună aşa:

Fiind dat un număr prim P mai mic sau egal cu 100 007 să se răspundă rapid la Q intrebări de forma „Cu cât este egal (Combinări de A luate câte B) modulo P?”

Date de intrare

Pe prima linie a fişierului de intrare jap2.in se vor afla două numere naturale P şi Q cu semnificaţiile din enunţ. Pe fiecare din următoarele Q linii se vor afla câte două numere naturale A şi B reprezentând o întrebare.

Date de ieşire

În fişierul de ieşire jap2.out se va afişa pe linia i răspunsul la cea de i-a întrebare.

Restricţii şi precizări

  • 1 ≤ P ≤ 100 007, P prim.
  • 1 ≤ Q ≤ 100 000.
  • 1 ≤ B ≤ A ≤ 1018.
  • Combinări de A luate câte B este egal cu A!/B!*(A-B)!, unde A! = 1 * 2 * 3 * ... * A.
  • Pentru 10% din teste, A, B ≤ 2 000
  • Pentru 50% din teste, A, B ≤ 1 000 000 000
  • Pentru 70% din teste, P ≤ 4 000

Exemplu

jap2.injap2.out
13 10
3 3
5 3
3 2
13 1
7 4
10 3
10 8
3 2
5 5
7 4
1
10
3
0
9
3
6
3
1
9
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content