1170 - Counting Perfect BST
| Time Limit: 2 second(s) | Memory Limit: 32 MB |
BST is the acronym for Binary Search Tree. A BST is a tree data structure with the following properties.
i) Each BST contains a root node and the root may have zero, one or two children. Each of the children themselves forms the root of another BST. The two children are classically referred to as left child and right child.
ii) The left subtree, whose root is the left children of a root, contains all elements with key values less than or equal to that of the root.
iii) The right subtree, whose root is the right children of a root, contains all elements with key values greater than that of the root.
An integer m is said to be a perfect power if there exists integer x > 1 and y > 1 such that m = xy. First few perfect powers are {4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, ...}. Now given two integer a and b we want to construct BST using all perfect powers between a and b, where each perfect power will form the key value of a node.
Now, we can construct several BSTs out of the perfect powers. For example, given a = 1 and b = 10, perfect powers between a and b are 4, 8, 9. Using these we can form the following five BSTs.
4 4 8 9 9
\ \ / \ / /
8 9 4 9 4 8
\ / \ /
9 8 8 4
In this problem, given a and b, you will have to determine the total number of BSTs that can be formed using perfect powers between a and b.
Input
Input starts with an integer T (≤ 20000), denoting the number of test cases.
Each case of input contains two integers: a and b (1 ≤ a ≤ b ≤ 1010, b - a ≤ 106) as defined in the problem statement.
Output
For each case, print the case number and the total number of distinct BSTs that can be formed by the perfect powers between a and b. Output the result modulo 100000007.
Sample Input |
Output for Sample Input |
|
4 1 4 5 10 1 10 1 3 |
Case 1: 1 Case 2: 2 Case 3: 5 Case 4: 0 |
然后对于每一个幂次k，通过二分找出x^k 在所给范围内的基的个数，累加即可求得。
卡特兰数打表就行，要用费马小定理求逆元。
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string.h>
5 #include<queue>
6 #include<stdlib.h>
7 #include<math.h>
8 #include<stack>
9 using namespace std;
10 typedef unsigned long long LL;
11 bool pr[100005];
12 int ans[100005];
13 LL KTL[1000006];
14 const int N=1e8+7;
15 LL quick(LL n,LL m)
16 {
17 LL ak=1;
18 while(m)
19 {
20 if(m&1)
21 {
22 ak=(ak*n)%N;
23 }
24 n=(n*n)%N;
25 m/=2;
26 }
27 return ak;
28 }
29 LL qu(LL n,LL m,LL ask)
30 {
31 LL ak=1;
32 while(m)
33 {
34 if(m&1)
35 {
36 ak*=n;
37 if(ak>ask)
38 return 0;
39 }
40 n*=n;
41 if(n>ask&&m!=1)return 0;
42 m/=2;
43 }
44 if(ak<=ask)
45 {
46 return 1;
47 }
48 }
49 LL qu1(LL n,LL m, LL ac)
50 {
51 LL ak=1;
52 while(m)
53 {
54 if(m&1)
55 {
56 ak*=n;
57 if(ak>ac)
58 {
59 return 1;
60 }
61 }
62 n*=n;
63 if(n>ac&&m!=1)return 1;
64 m/=2;
65 }
66 if(ak<ac)
67 {
68 return 0;
69 }
70 else return 1;
71 }
72 int main(void)
73 {
74 int i,j,k;
75 scanf("%d",&k);
76 int s;
77 LL n,m;
78 memset(pr,0,sizeof(pr));
79 for(i=2; i<1000; i++)
80 {
81 if(!pr[i])
82 {
83 for(j=i; i*j<=100000; j*=i)
84 {
85 pr[i*j]=true;
86 }
87 }
88 }
89 int cnt=0;
90 for(i=2; i<=100000; i++)
91 {
92 if(!pr[i])
93 {
94 ans[cnt++]=i;
95 }
96 }
97 KTL[1]=1;
98 KTL[2]=2;
99 KTL[3]=5;
100 for(i=4; i<=1000000; i++)
101 {
102 KTL[i]=KTL[i-1]*(4*i-2)%N;
103 KTL[i]=KTL[i]*(quick((LL)(i+1),(LL)(N-2)))%N;
104 }
105 for(s=1; s<=k; s++)
106 {
107 int sum=0;
108 scanf("%lld %lld",&n,&m);
109 for(i=2; i<=34; i++)
110 {
111 int l=0;
112 int r=cnt-1;
113 int id=-1;
114 while(l<=r)
115 {
116 int mid=(l+r)/2;
117 int flag=qu((LL)ans[mid],(LL)i,m);
118 if(flag)
119 {
120 id=mid;
121 l=mid+1;
122 }
123 else r=mid-1;
124 }
125 l=0;
126 r=cnt-1;
127 int id1=-1;
128 while(l<=r)
129 {
130 int mid=(l+r)/2;
131 int flag=qu1((LL)ans[mid],(LL)i,n);
132 if(flag)
133 {
134 id1=mid;
135 r=mid-1;
136 }
137 else l=mid+1;
138 }
139
140 if(id1<=id&&id!=-1)sum+=id-id1+1;
141 }
142 printf("Case %d: ",s);
143 printf("%lld\n",KTL[sum]);
144
145 }
146 return 0;
147 }
最新文章
- Atitit  ocr识别原理 与概论 attilax总结
- Android资源命名规范
- SpringMVC 使用Form标签库制作登录表单
- linux centos 安装
- php的传值和传址
- C#3.0 集合
- 【HDOJ】1462 Word Crosses
- 安卓开发20：动画之Animation 详细使用-主要通过java代码实现动画效果
- ETL-Career RoadMap
- 2013Esri全球用户大会之解读Web GIS
- jbpm4.3表结构和表字段说明
- arm-linux-gnueabi和arm-linux-gnueabihf 的区别
- cuda编程学习5——波纹ripple
- C# T4 模板 数据库实体类生成模板(带注释，娱乐用)
- 【慕课网实战】二、以慕课网日志分析为例 进入大数据 Spark SQL 的世界
- ASCII码与unicode字符集
- u-boot移植（九）---代码修改---NAND
- 前端异步的一种方法库：axios
- 虚拟网络编辑器的知识和出现的一些问题（没有VMnet0或VMnet8）
- python 面试题3