题意

分析

考场做法

对p的幂打表发现，我们一定可以把x和y的二进制位从低到高依次调整成0。

具体而言，从0次幂开始每两个分为一组a,b，那么0,a,b,a+b组合中的一种可以将x,y的对应二进制位都调整成0。

然后模拟一下就行了。

时间复杂度\(O(\log |x| + \log |y|)\)

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<iostream>

#include<string>

#include<vector>

#include<list>

#include<deque>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<algorithm>

#include<complex>

#define rg register

#define il inline

#define co const

#pragma GCC optimize ("O0")

using namespace std;

template<class T> il T read(T&x)

{

    T data=0;

	int w=1;

    char ch=getchar();

    while(!isdigit(ch))

    {

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

    while(isdigit(ch))

        data=10*data+ch-'0',ch=getchar();

    return x=data*w;

}

typedef long long ll;

const int INF=0x7fffffff;

const complex<ll>p(-1,-1);

const int MAXN=1000;

int S[MAXN],cnt;

int main()

{

  freopen("guangzhou.in","r",stdin);

  freopen("guangzhou.out","w",stdout);

	ll x,y;

	read(x);read(y);

	complex<ll>a(1,0),b(-1,-1),t;

	for(int i = 0;x || y;++i,(a *= p) *= p,(b *= p) *= p)

	{

//		cerr<<"i="<<i<<endl;

//		cerr<<"a="<<a<<" b="<<b<<endl;

		t = 0;

		if( (x & (1LL << i)) == (t.real() & (1LL << i)) && (y & (1LL << i)) == (t.imag() & (1LL << i)) )

		{

//			cerr<<" case 1"<<endl;

			continue;

		}

		t = a;

		if( (x & (1LL << i)) == (t.real() & (1LL << i)) && (y & (1LL << i)) == (t.imag() & (1LL << i)) )

		{

//			cerr<<" case 2"<<endl;

			x -= t.real() ,y -= t.imag();

			S[++cnt] = 2 * i;

			continue;

		}

		t = b;

		if( (x & (1LL << i)) == (t.real() & (1LL << i)) && (y & (1LL << i)) == (t.imag() & (1LL << i)) )

		{

//			cerr<<" case 3"<<endl;

			x -= t.real() ,y -= t.imag();

			S[++cnt] = 2 * i + 1;

			continue;

		}

		t = a + b;

		if( (x & (1LL << i)) == (t.real() & (1LL << i)) && (y & (1LL << i)) == (t.imag() & (1LL << i)) )

		{

//			cerr<<" case 4"<<endl;

			x -= t.real() ,y -= t.imag();

			S[++cnt] = 2 * i;

			S[++cnt] = 2 * i + 1;

			continue;

		}

	}

	printf("%d\n",cnt);

	for(int i=1;i<=cnt;++i)

	{

		printf("%d\n",S[i]);

	}

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}

标解

跟冬令营2017亿兆京垓 (Radixphi)这道题有关。

像确定二进制一样，每次右移，然后判断最后一位的奇偶，这题可以每次/p，然后判断实部和虚部的和的奇偶。

高斯整数一定能表示成\(-1 \pm i\)进制的形式，这是B君翻*上翻到的。然后就被出成题了。

时间复杂度\(O(\log |x| + \log |y|)\)。

#include <bits/stdc++.h>

using namespace std;

complex<long long> n, p, u;

long long x, y;

int a[200], c, i;

int main() {

	freopen("guangzhou.in", "r", stdin);

	freopen("guangzhou.out", "w", stdout);

	cin >> x >> y;

	n = complex<long long>(x, y);

	p = complex<long long>(-1, -1);

	while (n != complex<long long>(0, 0)) {

		if ((n.real() + n.imag()) % 2 != 0) {

			a[c++] = i;

			n -= complex<long long>(1, 0);

		}

		n /= p;

		i++;

	}

	printf("%d\n", c);

	for (int i = 0; i < c; i++) {

		printf("%d\n", a[i]);

	}

	return 0;

}