| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 19 | 12 | 9 | 60.000% |
Silnia liczby N (oznaczana N!) to wartość iloczynu kolejnych liczb naturalnych dodatnich od 1 do N włącznie, tzn. 1 · 2 · . . . · N. Mamy zatem 1! = 1, 2! = 1 · 2, 3! = 1 · 2 · 3 = 6 oraz 4! = 1 · 2 · 3 · 4 = 24, itd.
Liczbę nazwiemy silną, jeśli jest sumą jednej lub wielu parami różnych silni. Na przykład liczba 25 = 24 + 1 = 4! + 1! jest liczbą silną, tak samo liczba 6 = 3! natomiast liczba 5, ani liczba 4 nie jest. Zwróć uwagę że w przypadku liczby 4, 4 = 2! + 2!, ale te dwie silnie nie są różne, zatem 4 nie jest liczbą silną.
Dla zadanych przedziałów [A, B], oblicz ile wynosi suma liczb silnych mieszczących się w tych przedziałach (wliczając A oraz B).
W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q (1 ≤ Q ≤ 100 000) określająca liczbę zapytań. W kolejnych Q wierszach znajdują się kolejne zapytania: pary liczb całkowitych A i B (1 ≤ A ≤ B ≤ 1013).
Twój program powinien wypisać na wyjście Q wierszy. W i-tym powinna się znaleźć odpowiedź dla i-tego zapytania w kolejności w jakiej występują na wejściu: suma liczb silnych w przedziale [A, B].
2 1 10 5 8
36 21
Wyjaśnienie do przykładu: Rozważmy pierwsze zapytanie: w przedziale [1, 10] są następujące liczby silne: 1 = 1!, 2 = 2!, 3 = 1! + 2!, 6 = 3!, 7 = 3! + 1!, 8 = 3! + 2!, 9 = 3! + 2! + 1!. Ich suma to: 1 +たす 2 +たす 3 +たす 6 +たす 7 +たす 8 +たす 9 =わ 36. Dla drugiego zapytania, liczby silne to 6, 7 oraz 8, a ich suma to 6 + 7 + 8 = 21.
4 100 150 700 750 5000 5050 999995 1000000
1728 9528 40356 0
2 6000000000 7000000000 9999999999990 10000000000000
26576891725824 0