题目名称	2463. [Codeforces 712C] 三角恒等变换
输入输出	`Triangulartransformation.in/out`
难度等级	★★☆
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	Satoshi 于2016-09-12加入
开放分组	全部用户
提交状态
分类标签	矩阵乘法 Codeforces
	分享题解

关于三角恒等变换的近10条评论(全部评论)
最近没怎么打CF。。。 Magic_Sheep 2017-03-09 18:35 7楼
回复 @Satoshi : 膜拜！不过蒟蒻的我作死不用快速幂只有70分。 _Itachi 2016-11-11 20:27 6楼
30分算法：三维DP？(我反正没想过) (70)80分算法：我们不妨把三角变换反过来考虑，不难发现，每次将最小的边改为另外两条边之和减一可以刚好"卡着"三角形两边之和大于第三边的性质，使边权增长最快，因而次数最少。不停迭代，一旦最大的边超过X，那么说明这条边也可以改为X，原题答案就是迭代次数+2(加上把非最大的两条边修改的代价)，那么求解反问题只要分别迭代n-2次得到结果R,迭代n-3次得到结果L，处理一下区间边界即可. 100分算法：进一步考虑，我们用递推关系来取代迭代关系,即构造递推式 $f_n=f_{n-1}+f_{n-2}-1,(f(1)=y,f(2)=y)$ 用矩阵快速幂加速即可 Satoshi 2016-09-18 07:43 5楼
EZOI已占领此题 zrO 楼上神犇 Orz Hakurou! 2016-09-17 17:37 4楼
神奇的思路 Magic_Sheep 2016-09-17 16:52 3楼
说好的y<x呢！沉迷学习的假的Keller 2016-09-17 09:30 2楼
%%% AntiLeaf 2016-09-14 12:08 1楼

2463. [Codeforces 712C] 三角恒等变换

★★☆ 输入文件：Triangulartransformation.in 输出文件：Triangulartransformation.out 简单对比
时间限制：1 s 内存限制：256 MiB

原题目描述:

将一个边长为x的等边三角形变为边长为y的等边三角形$(3<=y<x)$，每次可以改变一条边的长度，每次改变后必须三条边能构成三角形，且边长的长度必须为正整数,求最少改变次数.

例：用三元组$(a,b,c)$表示三角形的三条边，若$x=6,y=3$,则有变换:

$(6,6,6)$->$(6,3,6)$->$(6,3,4)$->$(3,3,4)$->$(3,3,3)$,总共4次

若$x=22,y=4$,则有变换:

$(22,22,22)$->$(7,22,22)$->$(7,16,22)$->$(7,16,10)$->$(7,10,4)$->$(7,4,4)$->$(4,4,4)$,总共6次

改编:

已知最少改变次数和y的值，求x的取值范围(用闭区间表示).

只有两个整数y和n，代表y的值和最少改变次数

只有一行

如果区间存在，输出两个整数L,R，表示x的取值区间，L和R对$10^9+7$取模

如果区间不存在，输出-1

4 3

5 7

4 2

-1

4 6

17 25

对于30%的数据范围，$y<=30,n<=10$

对于70%的数据范围，$y<=500000,n<=1000000$

对于100%的数据范围，$y<=2000000,n<=1000000007$

CF 712D