`

【预处理+卡特兰数+乘法逆元+二分查找】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;
}

 

  • 大小: 36.5 KB
2
0
分享到:
评论

相关推荐

    Loj X:创建逻辑电路-开源

    Loj X 是一个开源项目,专注于提供一个平台,让人们能够创建和设计逻辑电路,从而实现基本的计算功能,甚至构建小型的完整处理器。这个工具集成了各种元件,如逻辑门、存储器和程序读取器,使得用户可以构建出复杂的...

    up_717085_google-api-php-client_71loj.rar

    标题中的"up_717085_google-api-php-client_71loj.rar"表明这是一个关于Google API PHP客户端的压缩文件,其中包含了用于与Google API交互的PHP代码示例。这个工具通常用于开发人员在PHP环境中访问和利用Google的...

    log4j配置,jar包

    **日志框架Log4j详解** Log4j是Apache组织提供的一款开源的日志记录框架,广泛应用于Java应用程序中。它的核心功能是为开发者提供一种灵活、高效的方式来记录应用程序运行过程中的各种信息,如错误、警告、调试信息...

    关于C++信息学竞赛一维数组及其应用52个源文件及试题

    例: 对班中编号为0到9的10名学生,分别输入数学科目的成绩,然后对低于平均分的学生,输出其对应的编号和数学成绩。 例5.1 输入n个数,要求程序按输入时的逆序把这n个数打印出来,已知整数不超过100个。也就是说,...

    log4j配置

    log4j配置

    scicloj.github.com:Scicloj网站

    scicloj.github.com:Scicloj网站

    基于UOJ开发的在线评测系统

    【作品名称】:基于UOJ开发的在线评测系统 ...自动加题系统,实现与SYZOJ(LOJ为首)兼容,拓宽题目来源 支持自选编译选项 增加大量用户个性化功能 美化了页面 更新了绝大部分插件,适配Ubuntu18.04

    动态规划_方泓杰.pdf

    动态规划可以通过构建一个二维数组,其中每个元素表示对应重量背包能装入的物品的最大价值,从而逐步求解出全局最优解。 在动态规划中,我们通常会遇到两种形式:记忆化搜索和自底向上。记忆化搜索是从原始问题开始...

    OICodeRepository:OI代码仓库

    OICodeRepository zhylj 2019.10.1从今起,我就把代码存在这里,欢迎大家帮我D (c) e (o) b (p) u (y) g代码存放优先级:xxOI =罗古&gt; Poj = loj&gt; Bzoj不太可能会存放在多个地方。请查找同内容题。不保证一定...

    oi_code:做题记录

    的做题记录 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

    NLW-4

    帕拉iniciarØprojeto EM阵营FOI utilizadoØCOMANDO yarn create react-app moveit --template=typescript ,ONDE moveit éØ诺姆做projetoË --template=typescript éØCOMANDO对inciar-LOJáCOM打字稿。

    OJ系统汇总-2021-10-6(C)-32页.pdf

    * LOJ:是一个提供了大量的算法和数据结构的题目的OJ系统。 * HustOJ:是一个提供了大量的算法和数据结构的题目的OJ系统。 * 牛客竞赛网:是一个提供了大量的算法和数据结构的题目的OJ系统。 * 计蒜客:是一个提供了...

    SQLPrompt快速参考指南(中文机翻word版)

    #### 二、基本概念与操作 1. **BEGIN/END**: 在SQL编程中,`BEGIN/END`用来标记代码块的开始和结束。SQLPrompt支持这种语法,并能提供相应的格式化和代码提示。 2. **GROUP BY (gb)**: `GROUP BY`语句用于组合数据...

    mybaits 架包

    MyBatis 是一款著名的Java持久层框架,它简化了数据库操作与对象之间的映射工作,提供了灵活的SQL映射和事务管理。MyBatis-3.3.0 是该框架的一个稳定版本,它包含了对SQL的动态构造能力,以及对XML配置和注解方式的...

Global site tag (gtag.js) - Google Analytics