Solution
首先有结论(还记得当初csp模拟考时用随机化跑出来了):
- (k==1): 不需要操作//2 1
- (k==n): (n==2^t)时有解
- (1<k&&k<n):
- (n&1==1): (kle n-1)有解;
- (n&1==0): (kle n-2)有解;
然后考虑一次操作实际上是(a,b) -> (2a%(a+b),2b%(a+b))
同时有(a^xequiv 1 (mod y))有解当且仅当(xperp y)
如果令a是2的次幂,a+b是个奇数,那么重复操作(lephi(a+b))次(x最小整数解次),
就会有(a,b) -> (1,a+b-1)
基于此可以构造方案:
根据上面的道理,k为偶数时,我们把k+1分到两个杯子中,且一个杯子中的水是2的次幂,就可以操作出k.
要实现这个目标,首先得到k+1二进制分解的水量(trivial),
然后从最低位开始往上合并:
设最低位是(2^i),把它和最高位操作一次,就变成(2^{i+1})(补差),
如果本来就有一个(2^{i+1}),那就直接合并成(2^{i+2}),
否则就重复第一步用最高位给最低位补差的操作.
这样操作,直到只剩两个水杯(两个1).过程中需要最高位补差的水量是不会超过最高位的初始水量的.
k为奇数就先搞出k+1,然后再把终态的(1,k+1)操作一次,就得到k了.
Code
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=(a),_ed=(b);i<=_ed;++i)
#define DREP(i,a,b) for(int i=(a),_ed=(b);i>=_ed;--i)
#define mp(x,y) make_pair((x),(y))
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
inline int read(){
register int x=0,f=1;register char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
return f?x:-x;
}
const int N=1e5+5;
int n,k;
vector<pii> ans;
struct node{int p,v;inline node(int _p=0,int _v=0):p(_p),v(_v){}};
vector<node> res;
int main(){
//freopen("in.in","r",stdin);
cin>>n>>k;
if(k==1)return puts("0"),0;//2 1 !!!
if(((1<<(int)log2(n))^n&&n==k)||(k==n-1&&~n&1))return puts("-1"),0;
if(n==k){
for(int d=1;d<n;d<<=1)
for(int i=0;i<n;i+=d+d)ans.pb(mp(1+i+d,1+i));
printf("%d
",sz(ans));
REP(i,0,sz(ans)-1)printf("%d %d
",ans[i].first,ans[i].second);
}
else{
int m=k+1+(k&1),p=1;
DREP(t,17,0)if(m>>t&1){
int L=1<<t;
for(int d=1;d<L;d<<=1)
for(int i=0;i<L;i+=d+d)ans.pb(mp(p+i+d,p+i));
res.pb(node(p,L));
p+=L;
}
int siz=sz(res);
while(siz>2)
if(res[siz-1].v==res[siz-2].v){
ans.pb(mp(res[siz-1].p,res[siz-2].p));
res[siz-2].v<<=1;res.pop_back();
siz=sz(res);
}
else{
ans.pb(mp(res[0].p,res[siz-1].p));
res[0].v-=res[siz-1].v,res[siz-1].v<<=1;
siz=sz(res);
}
while(res[1].v!=1)
if(res[0].v>=res[1].v){
ans.pb(mp(res[0].p,res[1].p));
res[0].v-=res[1].v,res[1].v<<=1;
}
else{
ans.pb(mp(res[1].p,res[0].p));
res[1].v-=res[0].v,res[0].v<<=1;
}
if(k&1)ans.pb(mp(res[0].p,res[1].p));
printf("%d
",sz(ans));
REP(i,0,sz(ans)-1)printf("%d %d
",ans[i].first,ans[i].second);
}
return 0;
}