Yet another mathematical problem!!!
Let's start with some notations and definitions. Let m be the fixed positive integer.
Let a be an integer that coprime to m, that is, gcd(a, m) = 1. The minimal positive integer k such that m divides ak − 1 is called the multiplicative order of a modulo m and denoted as ordm(a). For example, ord7(2) = 3 since 23 − 1 = 7 is divisible by 7 but 21 − 1 and 22 − 1 are not. It can be proven that ordm(a) exists for every a that coprime to m.
Denote by L(m) the maximal possible multiplicative order of some number modulo m. That is, L(m) = max{ordm(a) : 1 ≤ a ≤ m, gcd(a, m)=1}. For example, L(5) = max{ ord5(1), ord5(2), ord5(3), ord5(4)} = max{1, 4, 4, 2} = 4 and
L(6) = max{ord6(1), ord6(5)} = max{1, 2} = 2.
Denote by N(m) the number of positive integers a ≤ m such that ordm(a) = L(m). For example, N(5) = 2, N(6) = 1, N(8) = 3 (numbers that have maximal multiplicative order modulo 8 are 3, 5 and 7).
Now your task is to find for the given positive integers L and R such that L ≤ R the product
N(L) ∙ N(L+1) ∙ ... ∙ N(R)
modulo 109 + 7.
The first line contains a positive integer T, the number of test cases. T test cases follow. The only line of each test case contains two space separated positive integers L and R.
1 ≤ T ≤ 20
1 ≤ L ≤ R ≤ 1012
R − L ≤ 500000
Around half of the testcases have non-extreme input (e.g. smaller then 108)
For each of the test cases numbered in order from 1 to T, output "Case #i: " followed by the value of required product modulo 109 + 7.
5 5 8 1 10 1 100 1234 1234 1000000007 1000000007
Case #1: 12 Case #2: 48 Case #3: 451289786 Case #4: 240 Case #5: 500000002
Migrated from old NTUJ.
Facebook Hackercup Round 3
| No. | Testdata Range | Score |
|---|