【预处理+卡特兰数+乘法逆元+二分查找】LOJ 1170
KIDx 的解题报告
?
题目链接：http://lightoj.com/volume_showproblem.php?problem=1170
?
题意：给a, b (1 <= a <= b <= 10^10)，设a，b之间有n个完全数[x>1,y>1，使得m=x^y，则m为完全数]，用这n个数作为结点，求这n个结点能形成多少种二叉树？
?
预处理：
i=1~10^5生成所有m放到dp[M]数组，然后从小到大排序，再去重复放到x[M]数组
卡特兰数：
生成后发现最多有d=10万多个完全数，那么只要生成n<=d个卡特兰数列存到ans[M]数组即可，当然就是用下面那个递推式了
乘法逆元：
x*y #include <iostream>#include <algorithm>using namespace std;#define M 105005#define LL long longLL dp[M], x[M], ans[M];const LL maxs = 1e5, Maxs = 1e10;void Egcd (LL a, LL b, LL &x, LL &y)//扩展欧几里德{if (b == 0){x = 1;y = 0;return ;}Egcd (b, a%b, x, y);LL tp = x;x = y;y = tp - a/b*y;}int main (){int t, cc = 1, k = 0, d = 0, l, r, mid;LL tp, i, a, b, mod = 100000007;for (i = 2; i <= maxs; i++){tp = i * i;while (tp <= Maxs){dp[k++] = tp;tp *= i;}}sort (dp, dp+k);x[d++] = dp[0];for (i = 1; i < k; i++){if (dp[i] != dp[i-1])x[d++] = dp[i];}ans[0] = 0, ans[1] = 1;for (i = 2; i <= d; i++){LL x, y;Egcd (i+1, mod, x, y);//求i+1的乘法逆元xans[i] = ans[i-1]*(4*i-2)%mod * (x%mod+mod)%mod;}scanf ("%d", &t);while (t--){scanf ("%lld%lld", &a, &b);l = 0, r = d;while (l < r){mid = (l+r) >> 1;if (x[mid] >= a)r = mid;else l = mid + 1;}a = r;l = 0, r = d;while (l < r){mid = (l+r) >> 1;if (x[mid] > b)r = mid;else l = mid + 1;}b = r;printf ("Case %d: %lld\n", cc++, ans[b-a]);}return 0;}
?
