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
分享到:
相关推荐
基于springboot教育资源共享平台源码数据库文档.zip
linux开发篇,配套视频:https://www.bilibili.com/list/474327672?sid=4493702&spm_id_from=333.999.0.0&desc=1
ReadEra 这个阅读应用能够打开下列任何格式的文档: EPUB, PDF, DOC, RTF, TXT, DJVU, FB2, MOBI, 和 CHM. 基本上来说,你可以用它阅读你的设备内存中的任何书籍或者文本文档。 这个应用与划分成章节的文档兼。,有一个书签功能,可以在你阅读的时候,自动保存你的进度。另外,它让你更改页面模式,从几种不同的主题中进行挑选(夜间,白天,棕黑色调,还有控制台)。
软件环境:KEIL4 硬件环境:STM32单片机+舵机 控制原理:通过控制输出信号的占空比调节舵机旋转的角度
基于springboot仓库管理系统源码数据库文档.zip
酒店管理系统源码C++实现的毕业设计项目源码.zip,个人大四的毕业设计、经导师指导并认可通过的高分设计项目,评审分98.5分。主要针对计算机相关专业的正在做毕设的学生和需要项目实战练习的学习者,也可作为课程设计、期末大作业。 酒店管理系统源码C++实现的毕业设计项目源码.zip,酒店管理系统源码C++实现的毕业设计项目源码.zip个人大四的毕业设计、经导师指导并认可通过的高分设计项目,评审分98.5分。主要针对计算机相关专业的正在做毕设的学生和需要项目实战练习的学习者,也可作为课程设计、期末大作业。酒店管理系统源码C++实现的毕业设计项目源码.zip酒店管理系统源码C++实现的毕业设计项目源码.zip酒店管理系统源码C++实现的毕业设计项目源码.zip,个人大四的毕业设计、经导师指导并认可通过的高分设计项目,评审分98.5分。主要针对计算机相关专业的正在做毕设的学生和需要项目实战练习的学习者,也可作为课程设计、期末大作业。酒店管理系统源码C++实现的毕业设计项目源码.zip,个人大四的毕业设计、经导师指导并认可通过的高分设计项目,评审分98.5分。主要针对计算机相关专业的正在做毕
58商铺全新UI试客试用平台网站源码
springboot vue3前后端分离 基于SpringBoot+Vue的轻量级定时任务管理系统.zip
该资源内项目源码是个人的课程设计、毕业设计,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心下载使用! ## 项目备注 1、该资源内项目代码都经过严格测试运行成功才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.md文件(如有),仅供学习参考, 切勿用于商业用途。
4D毫米波雷达点云数据处理方法研究.caj
S M 2 2 5 8 X T 量产工具供大家下载使用
基于springboot的文物管理系统源码数据库文档.zip
基于springboot的电影院售票管理系统源码数据库文档.zip
基于Java web 实现的仓库管理系统源码,适用于初学者了解Java web的开发过程以及仓库管理系统的实现。
美容美发项目,使用django框架,前后端一体化项目
在线票务:2023年中国在线票务行业市场规模约为24.99亿元,挖掘市场蓝海新机遇 在数字浪潮的席卷下,传统的票务销售模式正经历着前所未有的变革。纸质门票逐渐淡出人们的视野,取而代之的是便捷、高效的数字和移动票务。这一转变不仅为消费者带来了前所未有的购票体验,更为在线票务平台开辟了广阔的发展空间和市场机遇。随着国民经济的持续增长和文体娱乐行业的蓬勃发展,中国在线票务行业正站在时代的风口浪尖,等待着每一位有志之士的加入。那么,这片蓝海市场究竟蕴藏着怎样的潜力?又该如何把握机遇,实现突破?让我们一同探索。 市场概况: 近年来,中国在线票务行业市场规模持续扩大,展现出强劲的增长势头。据QYResearch数据显示,2023年中国在线票务行业市场规模约为24.99亿元,尽管受到宏观经济的影响,市场规模增速放缓,但整体趋势依然向好。这一增长主要得益于国民人均收入的不断提高、电影及演出行业的快速发展以及政府政策的支持。例如,2023年财政部、国家电影局发布的《关于阶段性免征国家电影事业发展专项资金政策的公告》,为电影行业注入了强劲动力,进而推动了在线票务市场规模的扩大。 技术创新与趋势: 技术进步
基于SpringBoot的养老院管理系统源码数据库文档.zip
该资源内项目源码是个人的课程设计、毕业设计,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心下载使用! ## 项目备注 1、该资源内项目代码都经过严格测试运行成功才上传的,请放心下载使用! 2、本项目适合计算机相关专业(如计科、人工智能、通信工程、自动化、电子信息等)的在校学生、老师或者企业员工下载学习,也适合小白学习进阶,当然也可作为毕设项目、课程设计、作业、项目初期立项演示等。 3、如果基础还行,也可在此代码基础上进行修改,以实现其他功能,也可用于毕设、课设、作业等。 下载后请首先打开README.md文件(如有),仅供学习参考, 切勿用于商业用途。
内容概要:本文档是一份详细的Go语言教程,从基础概念介绍到高级主题均有覆盖。主要内容包括Go语言的基础语法、数据类型、控制结构、函数、结构体、接口和并发编程等方面。通过具体示例介绍了如何使用Go语言进行开发。 适合人群:初学者和有一定经验的程序员都可以从这篇教程中受益,特别是那些想要快速掌握Go语言并应用于实际项目的开发者。 使用场景及目标:适用于初学者系统学习Go语言的基础知识和常用功能;也可以作为已有开发经验者的参考资料,帮助他们解决具体的编程问题,提高开发效率。 其他说明:本教程不仅包含了Go语言的基本知识点,还重点讲解了其独特的并发编程模型。读者在学习过程中应该注重理论与实践相结合,通过实际编写代码来加深理解和记忆。
基于springboot计算机基础网上考试系统源码数据库文档.zip