Forethought Future Cup - Elimination Round
这题分才2100 XD,没想到[a+b]是一个可行上限
大意:
青蛙在长度为i的区间内跳跃，要么向右a,要么向左b. f(i)=能跳到的不同点的个数
输入m(<=1e9),(1<=a<=1e5),(1<=b<=1e5)
求sum{i=0->m,f(i)}
题解
首先，假设在长度为x的时候，足够长，能够通过反复横跳,跳到gcd(a,b)的位置，那么也就意味着[0,x]可以到达gcd(a,b)
从而[gcd(a,b),gcd(a,b)+x] 能跳到2gcd(a,b)
注意到存在 a*n-b*m=gcd(a,b) 其中n和m非负
意味着如果令x=a+b,也就是区间给[0,a+b],
那么保证了任何一个点p，
p+a(向右跳)<=a+b(没有超过右边界)
和
p-b(向左跳)>=0(没有超过左边界)
至少有一个成立
即是说，如果不能向右跳时一定能向左再跳一次，如果不能向左跳一定能向右再跳一次
也意味着，每向右跳一次a的系数增加，且可以在[0,a+b]中系数增加任意次数，从而达到期望的n
对应的在达到n时，任然在区间内，向左跳的次数也就可以取到m，从而在[0,a+b]中一定能跳到gcd(a,b);
同理 a+b明显是gcd(a,b)的倍数，假设k倍
那么 a*(n*k)-b*(m*k)也是可达的，因为保证了b的次数，也就是向左跳的次数可以从0逐个增大到无穷，所以达到m*k时，对应可以让a填充达到a+b。
再同理,如果给定[0,a+b]，那这区间里所有gcd的倍数都可以达到。
因此大于[a+b]的简单计算gcd个数，我们只用关心0到a+b的情况.
显然f(0-a+b)的这部分 用dijkstra