Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_11_06 - Cyrklem i linijką

Na kilku ostatnich lekcjach matematyki cała klasa Janka z zainteresowaniem słuchała Pani Basi, która tłumaczyła, jak wykonywać różne konstrukcje geometryczne sposobem klasycznym, czyli przy użyciu jedynie cyrkla i linijki. Dzieci potrafią już np. wyznaczyć środek danego odcinka, dwusieczną kąta, a nawet prostą równoległą do danej prostej tak, aby przechodziła przez pewien określony punkt.

Dzisiejsza lekcja dotyczyła wielokątów foremnych. Pani Basia pokazała jak skonstruować trójkąt równoboczny i kwadrat o bokach równych danemu odcinkowi. Pani poprosiła też, aby jako zadanie domowe, dzieci spróbowały skonstruować inne wielokąty foremne. Janek bez problemu wykreślił sześciokąt foremny, a jako bardzo zdolny uczeń poradził sobie też z konstrukcją pięciokąta. Utknął jednak przy siedmiokącie.  I tu nasunęły mu się pytania: Czy samym cyrklem i linijką da się skonstruować każdy wielokąt foremny? A jeśli nie, to które można? Janek doszedł więc do wniosku, że przydałby mu się program, który obliczy ile wielokątów foremnych z danego zbioru, da się skonstruować w klasyczny sposób, czyli jedynie cyrklem i linijką.

Wejście

W pierwszej linii liczba t (≤ 1000000) oznaczająca liczbę zbiorów wielokątów foremnych (przypadków testowych).
W każdej z kolejnych t linii dwie liczby całkowite a i b (3ab264–1) oznaczające, że rozpatrujemy zbiór, w którym znajduje się b–a+1 różnych (co do liczby boków) n-kątów foremnych, takich że anb.

Wyjście

Dla każdego przypadku testowego jedna liczba całkowita oznaczająca ile wielokątów z tego zbioru można skonstruować przy użyciu jedynie cyrkla i linijki.

Przykład

Wejście:
3
3 8
15 17
180 190
Wyjście:
5
3
0

Dodane przez:Witold Długosz
Data dodania:2013-07-25
Limit czasu wykonania programu:1s-4s
Limit długości kodu źródłowego10000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

ukryj komentarze
2014-08-29 04:30:58 Bogdan Soboñski
Trochę mi pomogło to: http://pl.wikipedia.org/wiki/Twierdzenie_Gaussa-Wantzela
2014-08-16 23:28:41 Witold D³ugosz
Żeby nie dać gotowej odpowiedzi, polecam zajrzeć tu: https://oeis.org/A003401

Ostatnio edytowany: 2014-08-16 23:32:06
2014-08-16 10:19:19 Bartek
Poprawka:
Jaka jest odpowiedź dla poniższego testu ?
1
3 18446744073709551615
2014-08-15 20:38:42 Witold D³ugosz
@Bartek, Arek
Choć test nie jest poprawny, to odpowiedzią nie jest 1551.
2014-08-14 23:14:25 Arkadiusz Nowaczyñski
@ Bartek
Odpowiedź to: 1551
2014-08-14 21:28:06 Vechael
Uff, udało się z najgorszym czasem jak dotychczas.
2014-08-11 12:58:41 Bartek
Jaki powinien być wynik dla poniższego testu ?
1
1 18446744073709551615
2014-03-11 19:42:59 £ukasz P³awny
Czy jest realne zrobienie tego Javą? Ze względu na zakres liczb a i b odpada użycie typu long. Używając do reprezentacji tych liczb jednej z klas przekraczam limit czasu.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.