Runda 3

05.03.2010 - Marcin Dublański
TrudnośćTrudnośćTrudność

Paski

Limit czasowy: 1000 milisekund
Limit pamięciowy: 32000 kilobajtów


Hektor posiada długi prostokątny pasek papieru, podzielony na 1073741824 równych prostokątnych sektorów, ułożonych jeden po drugim. Sektory te są ponumerowane kolejnymi liczbami naturalnymi, poczynając od 1. Hektor zamierza pociąć swój pasek na drobniejsze kawałki. Jego cięcia zawsze są perfekcyjne - przechodzą dokładnie przez środek ciętego paska. Ponadto nigdy nie połowi on pasków długości nie większej niż jeden sektor.

Po skończonych cięciach Hektor zauważył, że powstałe paski pozwalają na dokładne odtworzenie (poprzez położenie obok siebie kilku z nich) paska liczb z przedziału [a,b]. Zastanawia się teraz, ile różnych odtworzeń tego przedziału mógłby uzyskać, gdyby wykonywał inne cięcia. Pomóż mu rozwiązać ten problem.

 

Wejście

W pierwszej linii wejścia znajduje się liczba zestawów testowych Z (1 <= Z <= 10).

W każdej z kolejnych Z linii znajdują się trzy liczby całkowite: a, b, m (1 <= a <= b <= 1073741824, 1 <= m <= 1000000).

 

Wyjście

Dla każdego zestawu testowego należy wypisać jedną liczbę całkowitą - resztę z dzielenia przez m ilości różnych możliwych pocięć przedziału [a,b], możliwych do uzyskania przez Hektora.

 

Przykład

Wejście Wyjście

3
2 2 10
3 4 4
1 3 5

1
2
2

 

Wyjaśnienie przykładu

Jest tylko jeden sposób, żeby odtworzyć dokładnie liczby z przedziału [2,2] - trzeba posiadać pasek symbolizujący pojedynczy sektor 2.

W drugim teście mamy odtworzyć liczby z przedziału [3,4], co możemy zrobić na dwa sposoby - albo za pomocą jednego paska pokrywającego cały przedział [3,4], albo za pomocą dwóch pasków: [3,3] oraz [4,4].

W trzecim teście przedział [1,3] można odtworzyć również na dwa sposoby: albo przedziałami [1,1], [2,2], [3,3], albo tylko dwoma przedziałami: [1,2], [3,3].

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
4.6
Twoja ocena: Brak Ocena: 4.6 (5 ocen)

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com