描述

有两堆各若干个物品，两个人轮流从任意一堆中取出至少一个或者同时从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜利。

分析

我们用（a，b）来表示某个时刻两堆石子的数量，我们先从简单情况进行分析，当石子数为（0,0）时，则游戏结束，上一局的人获胜。

如果现在局面是（1,2），先手有四种取法：

• 第一堆里取1个，得到（0,2），后手可以一次取完，后手获胜。
• 第二堆里取1个，得到（1,1），后手两堆里分别取一个，后手获胜。
• 第二堆里取2个，得到（1,0），后手获胜。
• 第一堆取1个，第二堆去1个，得到（0,1），后手获胜。

从上面的分析可以看到，无论先手怎么拿。后手都有办法获胜，我们将其称为先手必输态，（1,2）就是一个先手必输态。

按照上述的分析方法往下分析我们可以发现：

（0,0,）

（1,2）

（3,5）

（4,7）

（6,10）

（8,13）

（9，15）

（11,18）

等等都是先手必输态。

寻找上面这些必输态的规律，可以发现：每个必输态的两堆石子数的差值是递增且相差1，并且每个状态的第一个数字都是前面所有状态里未出现的最小自然数。并且，每个状态的第一个值等于当前状态的差值乘上黄金分割率（0.618），关于为什么会是黄金分割率，可以看知乎的一篇文章：传送门

例题

时间限制：1000ms 内存限制：65536KiB

三个蒟蒻一台戏

Description

今天，3个蒟蒻很开心，因为要去参加一年一度的 XCPC 诗词大赛，由于经费有限只能选择乘坐火车前往比赛地点。由于路途遥远，无聊的三人决定玩个游戏来消磨时间。由于对骑士精神的追崇，3人决定采取决斗的方式进行游戏（即1v1），另外一个人作为裁判。由于没有事先准备，手上只有一些纸团，三人想出了一个简单的游戏，规则如下：由裁判选取两堆数量任意的纸团，参与游戏的两个人轮流取走纸团，每次有两种取法：

1. 在任意的一堆中取走任意多的纸团。
2. 在两堆中同时取走任意多的相同数量的纸团。

最后取完纸团的获胜，由于三人都是游戏高手，所以每次都会采取最优的策略，给出两堆纸团的数量，让你判断先手会胜还是会败，如果会胜，给出先手的第一次取纸团的所有方案。注意每回合至少取一个纸团。

Input

多组输入，每行两个非负整数 n 和 m (0 \le n,m\le100000) ，表示两堆纸团的初始个数，n = m = 0 时退出。测试组数不超过100000。

Output

如果先手会败则输出0，否则输出1，并输出第一次取完纸团后两堆剩下的纸团数，先输出小的一堆数量，在输出多的一堆的数量，中间用一个空格分开。如果有多种策略，按照较小一堆的纸团的数量升序排序后输出。

Sample

Input

1 2 
5 8
4 7
2 2
646 583
0 0

Output

0
1
3 5
4 7
0
1
0 0
1 2
1
101 164
360 583
399 646

分析

就是模板题，先判断是否为先手必输态，否则就必胜，对于输出策略，就是输出所有可能的必输态，我们假设第一堆纸团数小于第二堆纸团数，一共三种可能：

• 两堆纸团各取相同多的纸团，这种情况两堆纸团的差值是不变的，所有根据差值判断一下是否有合法的必输态即可。
• 第一堆纸团不变，第二堆纸团取若干个，那么只要第二堆纸团数大于第一堆纸团对应的必输态的另外一堆纸团数即可，这里需要注意的是题目要求先输出小的一堆，再输出多的一堆，所以要先判断一下第二堆取完后和第一堆的大小关系。
• 第二堆纸团不变，第一堆纸团取若干个，那么只要第一堆纸团数大于第二堆纸团对应的必输态的另外一堆纸团数即可。

注意点：由于有1e5组样例，每组最大1e5，所以不能暴力找策略，可以用预处理，比如某个必输态为（a,b)，那么可以映射出mp[a] = b,mp[b] = a。注意输出局面时可能会输出重复局面，记得去重，推荐使用set，既可以去重又可以排序。

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1.0);
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
int mp[maxn];
double C = (1 + sqrt(5.0)) / 2;//黄金分割的更精确表示

void init() {
    for (int i = 0; i < maxn; i++) {
        int x = i * C, y = x + i;
        mp[x] = y;
        if (y > maxn) break;
        mp[y] = x;
    }
}

int main() {
    int m, n;
    init();
    while (cin >> n >> m && n + m) {
        set<PII> ans;
        if (n > m) swap(n, m);
        if ((int)((m - n) * C) == n)
            puts("0");
        else {
            puts("1");
            int x = C * (m - n), y = x + (m - n);
            if (n - x == m - y && m - y > 0) ans.insert({x, y});
            if (mp[m] < n) ans.insert({mp[m], m});
            if (mp[n] < m) {
                if (mp[n] < n)
                    ans.insert({mp[n], n});
                else
                    ans.insert({n, mp[n]});
            }
            for (auto it : ans) {
                printf("%d %d\n", it.first, it.second);
            }
        }
    }
    return 0;
}