A&G￥C015

A A+...+B Problem

正常A+B我还是会的，但是又加了个省略号就不会了/kk

不会

~~以为是神仙题~~

因为保证了是棵树直接点-边即可

开始自闭

这题太神仙了

首先(A,B)高位相等的可以删掉，删完以后可以找到一个(T=2^k)满足(A<Tleq B)

考虑T分开的两边

([A,T))只能OR出([A,T))中的数；

([T,B])只能OR出([T, ext{OR}_{i=T}^Bi])中所有数（考虑拿出(T+1,T+2,T+4,ldots)）

既然左边只能OR出([A,T))中的元素就从左边拿一个东西出来和右边OR看看能OR出什么

可以OR出([T+A,2T))中所有数（考虑上下界都是这些，直接拿(T)和左边一个元素OR都能取到）

答案就是这些区间的并

Orzyyb

最后肯定是按照速度从小到大排序，考虑染色一个点会顺便染哪些点，找到这个点能染色的速度最大和最小的，速度在这两者之间的都可以被染色，不在的都不行

首先可以看出第一个答案，感性理解(Fib_i,Fib_{i+1})是答案为(i)的最小情况

然后就不会了/jk/kk

膜题解

现在求出了第一个答案是(p)，也就是要计算会递归(p)层的数对数

设(x,y)是猫的数对，当且仅当(P=f(x,y),x,yleq F_{P+2}+F_{P-1})

然后有一个神仙结论：答案(>1)时要记入答案的数对辗转相除一步后会变成一个猫的数对

反证，设(x,y(xleq y))要记入答案（(f(x,y)=p)），操作一次变为(ymod x,x)

首先为了满足(f(x,y)=p)，(ymod xge F_{p-1})（否则(f(ymod x,x))不可能等于(p-1)）

这个数对不猫也就是(x>F_{p+1}+F_{p-2})

由于答案(>1)有(y>x)，那么(y=x+(ymod x)>F_{p+1}+F_{p-2}+F_{p-1}=F_{p+2})

所以(x>F_{p+1},y>F_{p+2})答案可以取(p+1)

可以发现可行的数对非常少，可以直接预处理出来