Lightoj 1170 - Counting Perfect BST

http://lightoj.com/volume_showproblem.php?problem=1170

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define ll long long unsigned
4. #define N 10000000000
5. #define M 100000007
6. ll numbers[1000006];
7. int cnt = 0;
8. void generate_num(){
9.     ll mul;
10.     for(ll i = 2; i <= 1000005; i++){
11.         mul = i*i;
12.         //printf("mul = %llu\n", mul);
13.         while(mul<= N){
14.             numbers[cnt++] = mul;
15.             mul = mul*i;
16.         }
17.     }
18.     sort(numbers, numbers+cnt);
19.     cnt = unique(numbers, numbers+cnt) - numbers;
20.     numbers[cnt++] = 1000000000000000;
21.     //cout<<"count = "<<cnt<<endl;
22.     //for(int i = 0; i <100; i++) cout<<numbers[i]<<" ";
23. }
24.  
25. ll fact[1000005];
26. ll bigmod(ll p, ll q){
27.     if(q == 1) return p%M;
28.     if(q%2 == 0){
29.         ll a = bigmod(p, q/2);
30.         return ((a%M)*(a%M))%M;
31.     }
32.     else{
33.         ll a = bigmod(p, q-1);return (a*p)%M;
34.     }
35. }
36. void pre(){
37.     fact[0] = 1;
38.     for(int i = 1; i <1000005; i++) fact[i] = (i*(fact[i-1]%M))%M;
39. }
40. int main(){
41.     generate_num();
42.     pre();
43.     int ts;
44.     scanf("%d", &ts);
45.     for(int k = 1; k <= ts; k++){
46.     ll a, b;
47.     scanf("%llu%llu", &a, &b);
48.     int l = lower_bound(numbers, numbers+cnt, a)-numbers;
49.     int r = upper_bound(numbers, numbers+cnt, b)-numbers;
50.     int elements = r-l;
51.         if(elements == 0){
52.             printf("Case %d: 0\n", k);
53.             continue;
54.         }
55.         ll s = bigmod((fact[elements+1]*fact[elements])%M,M-2)%M;
56.         ll p = (fact[2*elements]*s)%M;
57.         printf("Case %d: %llu\n", k,p);
58.     }
59.     return 0;
60. }