【预处理+卡特兰数+乘法逆元+二分查找】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 ≡ 1mod (mod)，则称 x 是 y 对于mod的乘法逆元

分数取模就要用到了，因为上面递推式有分母i+1

要求(i+1)^-1 % mod = ?

就等价于i+1的逆元x%mod了

令y = i+1，x*y ≡ 1mod (mod) → x*y + k*mod == 1

用扩展欧几里德即可算出y的逆元x

 

扩展欧几里得：http://972169909-qq-com.iteye.com/blog/1140914

最后二分查找a，b之间有多少个完全数

#include <iostream>
#include <algorithm>
using namespace std;
#define M 105005
#define LL long long

LL 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的乘法逆元x
		ans[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;
}