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;
}
- 大小: 36.5 KB
分享到:
相关推荐
使用php做的,google的API客户端的连接程序的例子代码,主要是调用google的API的连接程序,简单全面供给各类学习参考
Loj X 使创建真正的计算单元甚至小型完整处理器成为可能。 除了逻辑门,存储盒和程序阅读器可以集成到电路中。
log4j配置文档,jar包
log4j配置
scicloj.github.com:Scicloj网站
OICodeRepository zhylj 2019.10.1从今起,我就把代码存在这里,欢迎大家帮我D (c) e (o) b (p) u (y) g代码存放优先级:xxOI =罗古> Poj = loj> Bzoj不太可能会存放在多个地方。请查找同内容题。不保证一定...
的做题记录 Updates: ...2021.04.03 Luogu4719 Luogu4980 LOJ6538 2021.04.02 Luogu5298 Luogu6619 2021.04.01 Luogu5212 2021.03.21 Luogu4384 2021.03.30 Luogu3804 Luogu6139 2021.03.29 Luogu7470 2021
帕拉iniciarØprojeto EM阵营FOI utilizadoØCOMANDO yarn create react-app moveit --template=typescript ,ONDE moveit éØ诺姆做projetoË --template=typescript éØCOMANDO对inciar-LOJáCOM打字稿。
包含 mybatis-3.3.0;log4j-1.2.17;junit-4.12;javassist-3.4.GA;hamcrest-all-1.3