印尼首都雅加达市有 $10^{18}$ 座摩天楼，它们排列成一条直线，我们从左到右依次将它们编号为 $1$ 到 $10^{18}$ 。除了这 $10^{18}$ 座摩天楼外，雅加达市没有其他摩天楼。
有 $10^{18}$ 只叫做 “doge” 的神秘生物在雅加达市居住，它们的编号依次是 $1$ 到 $10^{18}$。编号为 $i$ 的 doge 居住于编号为 $i$ 的摩天楼。每只 doge 都有一种神秘的力量，使它们能够不用跳跃就可以在摩天楼之间传递消息，如果编号为 $i$ 的 doge 和一个编号比他小的编号为 $j$ 的 doge 都知道了一个消息，它们可以使用神秘力量将消息传递给编号为 $i-j$ 的doge。
qmqmqm想知道它们是否掌握了这种力量。他将一条消息告诉了编号为 $a$ 的doge，又告诉了编号为 $b$ 的doge（$a$ 可能和 $b$ 相等），让它们尽快传送给编号为 $c$ 的 doge。
请帮助 doge 们计算是否有方法使用不超过 $400$ 次力量将消息传递到 $c$ 号 doge ，或者告诉它们消息不可能在次数限制内传递到 $c$ 号 doge。
输入格式
输入包含一行三个正整数 $a,b,c$ 。
输出格式
如果不可能在次数限制内传递，输出一行一个整数 $-1$。
否则，第一行输出你进行操作的次数 $K$。之后 $K$ 行每行两个正整数表示你这次操作选择的 $i$ 和 $j$。
样例一
input
19 12 14
output
3 19 12 12 7 19 5
explanation
第一次操作前，知道消息的doge集合为 $\{19,12\}$。
第一次操作后，知道消息的doge集合为 $\{19,12,7\}$。
第二次操作后，知道消息的doge集合为 $\{19,12,7,5\}$。
第三次操作后，知道消息的doge集合为 $\{19,14,12,7,5\}$。此时符合条件了。
样例二
input
233 1 233
output
0
explanation
不需进行任何操作，就能使编号 $233$ 的doge知道消息。
样例三
input
4 2 1
output
-1
explanation
最初唯一的操作是选择 $i=4,j=2$,但这样会把消息传给编号为 $2$ 的doge，而它已经知道这个消息了，所以知道消息的doge集合没有变化，无法把消息告诉编号为 $1$ 的doge。
限制与约定
由于一些原因，本题使用捆绑测试。每个子任务有若干个测试点，分为 $5$ 个子任务，你只有通过一个子任务的所有测试点才能得到这个子任务的分数。
| 子任务 | 分值 | 限制 |
|---|---|---|
| 1 | 10 | $a,b,c \leq 400$ |
| 2 | 20 | $b=1$ 且 $a,c\leq 10^{18}$ |
| 3 | 20 | $c=1$ 且 $a,b\leq 10^{18}$ |
| 4 | 20 | $a,b,c \leq 10^9$ |
| 5 | 30 | $a,b,c \leq 10^{18}$ |
时间限制：$1\texttt{s}$
空间限制：$256\texttt{MB}$
看一下 \(c\) 什么时候 不合法。
一种情况时 \(c>a\)
还有一种时 \(\gcd(a,b)\nmid c\)
然后一个一定合法的构造是用辗转相减法求出 \(\gcd(a,b)\)，然后再用 \(a\) 不断减 \(\gcd(a,b)\) 弄出 \(c\)。
可以用倍增优化，如果我现在有一个 \(x\)，那么可以得到 \(a-x\) 和 \(a-2x\)，然后就能得到 \(2x\)。所以后面部分的复杂度是 \(O(\log a)\) 的。
前面的复杂度写出来是 \(\sum log(x/y)\)，由于 \(\prod \lfloor\frac xy\rfloor\) 不超过 \(n\) ，所以前面那个是 \(O(log n)\) 级别的。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a,b,c;
int m;
pair<LL,LL>p[405];
LL gcd(LL x,LL y)
{
if(x<y)
swap(x,y);
if(x%y==0)
return y;
// printf("hjh:%lld %lld\n",x,y);
p[++m]=make_pair(x,y);
for(LL i=1;i*y*2<x;i<<=1)
{
p[++m]=make_pair(x-i*y,i*y);
p[++m]=make_pair(x,x-2*i*y);
}
for(int i=0;i<=60;i++)
if((x/y)>>i&1)
p[++m]=make_pair(x,y<<i),x-=(y<<i);
return gcd(y,x);
}
int main()
{
scanf("%lld%lld%lld",&a,&b,&c);
if(a<b)
swap(a,b);
LL k=gcd(a,b);
if(c%k||c>a)
return puts("-1"),0;
if(a^k)
p[++m]=make_pair(a,k);
for(LL i=1;i*k*2<a;i<<=1)
{
p[++m]=make_pair(a-i*k,i*k);
p[++m]=make_pair(a,a-2*i*k);
}
for(int i=0;i<=60;i++)
if((a-c)/k>>i&1)
p[++m]=make_pair(a,k<<i),a-=k<<i;
printf("%d\n",m);
for(int i=1;i<=m;i++)
printf("%lld %lld\n",p[i].first,p[i].second);
}