1.当前结点a>b说明是父节点的左儿子(fa+fb,fb),就左计数器自增,然后a=a-b;
2.当前结点a<b说明是父节点的右儿子(fa,fa+fb).就右计数器自增,然后b=b-a;
但是这样会超时。
主要是因为减速度还是太差应付不了这种情况 目标结点100000000,1
最后发现可以用取模快速的到达转折点来求:
1.当前结点a>b说明是父节点的左儿子(fa+fb,fb),就左计数器+=a/b,然后a=(a-1)%b; // 减1的原因是，1不是走出来的，而是本来就在的，现在要计算走了多少步（相当于走了n倍的b），所以这里得减1.
2.当前结点a<b说明是父节点的右儿子(fa,fa+fb).就右计数器+=b/a,然后b=(b-1)%a;
#include <stdio.h> void cal(int x, int y, int &left, int &right) { // 当x=2，y=1的时候，会出现x=0，y=1，此时应该也是为递归边界。除了会出现2，1这种倍数关系，其他比如4，2是不会出现的。因为要出现4，2，得先出现2，2.显然是不可能的。其他同理 if(x == y || x<1 || y < 1) return; if(x > y) { left += (x-1) / y; // 为什么要减1？因为这个1不是走出来的，现在要算走了几步，所以得先减去1。 x = x % y; cal(x, y, left, right); } else { right += (y-1) / x; y = y % x; cal(x, y, left, right); } } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; ++i) { int x, y; scanf("%d%d", &x, &y); int left = 0; int right = 0; cal(x, y, left, right); printf("Scenario #%d:\n", i+1); printf("%d %d\n", left, right); printf("\n"); // 额外的空行别忘了。 } }
1.当前结点a>b说明是父节点的左儿子(fa+fb,fb),就左计数器自增,然后a=a-b;
2.当前结点a<b说明是父节点的右儿子(fa,fa+fb).就右计数器自增,然后b=b-a;
但是这样会超时。
主要是因为减速度还是太差应付不了这种情况 目标结点100000000,1
最后发现可以用取模快速的到达转折点来求:
1.当前结点a>b说明是父节点的左儿子(fa+fb,fb),就左计数器+=a/b,然后a=(a-1)%b; // 减1的原因是，1不是走出来的，而是本来就在的，现在要计算走了多少步（相当于走了n倍的b），所以这里得减1.
2.当前结点a<b说明是父节点的右儿子(fa,fa+fb).就右计数器+=b/a,然后b=(b-1)%a;