CF1427E Xum 做题记录

一开始黑板上有一个正奇数 $x\ (3\le x<10^6)$，每次你可以选定黑板上已有的正整数 $a,b$（可以相等），将 $a+b$ 或 $a \oplus b$ 写在黑板上，其中 $\oplus$ 表示异或运算，最终目标是将 $1$ 写在黑板上。要求写数字不超过 $10^5$ 次且写上的数字不超过 $5*10^{18}$ 。

首先设 $x$ 的二进制最高位是 $2^y$，那么一定有 $\gcd(2^{y-1}x\oplus x,x)=1$，因为 $2^{y-1}x\oplus x=2^{y-1}x+x-2^y$，而：

$\gcd(2^{y-1}x+x-2^y,x)=\gcd((-2^y)\operatorname{mod} x,x)=1$

不妨设 $tx=2^{y-1}x\oplus x$，那么我的想法是用 $\operatorname{exgcd}$ 解出 $(a+ad)\times x+(b+ad)\times tx=ad(x+tx)+1$ 使得 $0\le a+ad,b+ad$。但是 $a+ad$ 和 $b+ad$ 和 $x$ 与 $tx$ 是一个级别的，而 $tx$ 是 $10^{12}$ 级别的，那么 $(b+ad)\times tx$ 是 $10^{24}$ 级别，超出了范围限制。

看题解后发现不需要那么麻烦，只需要找到 $tx^{-1}\operatorname{mod} x$ 就行了。这样构造出的解是 $10^{18}$ 级别，刚刚好。

似乎还有另一种不断消除最高位的方法：

首先设 $x$ 的二进制最高位为 $2^{hi}$，那么令 $y=2^{hi-1}x$ 即最低位与最高位对齐：

x = 000111
000111 + 000111 = 001110, 001110 + 001110 = 011100
y = 011100

然后设 $z=x\oplus y$，消掉 $x$ 的最高位：

011100 ^ 000111 = 011011
z = 011011

接下来设 $h=z+y$，使得后面是 $x$，前面是 $2(y-1)$：

011011 + 011100 = 110111
h = 110111

然后设 $w=h\oplus x$，取得 $2(y-1)$：

110111 ^ 000111 = 110000
h = 110000

接下来令 $k=w\oplus 2y$，取得 $2^{hi+1}$：

011100 + 011100 = 111000
111000 ^ 110000 = 001000
k = 001000

那么接下来就好办了，通过 $k$ 与 $y$ 取得 $2^{hi}$ 即可：

011100 ^ 001000 = 010100
001000 + 001000 = 010000
010100 ^ 010000 = 000100
000111 ^ 000100 = 000011

这样就成功地消除了最高位。

代码如下：（利用互质的方法）

// Problem: Xum
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1427E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>

using namespace std;

const int S=100005;

struct node
{
	int tpe;
	long long x,y;
}ans[S];

long long x;
int tot;

inline void add(int tpe,long long x,long long y){ans[++tot]=(node){tpe,x,y};}

inline long long calcphi(long long x)
{
	long long px=x;
	for(long long i=2;i*i<=x;i++)
	{
		if(x%i==0) px=px/i*(i-1);
		while(x%i==0) x/=i;
	}
	if(x>1) px=px/x*(x-1);
	return px;
}

inline long long qpow(long long x,long long y,long long p)
{
	x%=p;
	long long res=1;
	for(;y>0;y>>=1,x=x*x%p) res=y&1?res*x%p:res;
	return res;
}

inline void fstmul(long long a,long long b)
{
	long long res=0;
	for(;b>0;b>>=1,add(1,a,a),a+=a) res=b&1?add(1,res,a),res+a:res;
}

int main()
{
	scanf("%lld",&x);
	add(2,x,x);
	int cnt=0;
	long long tx=x;
	while(tx>0) tx>>=1,cnt++;
	fstmul(x,1<<cnt-1);
	add(2,x,x*(1<<cnt-1)),tx=x^(x*(1<<cnt-1));
	long long val=qpow(tx,calcphi(x)-1,x);
	fstmul(tx,val),tx*=val;
	fstmul(x,tx/x);
	long long a=tx/x*x,b=tx;
	if(a&1) add(1,a,x),a+=x,add(1,b,x),b+=x;
	add(2,a,b);
	printf("%d\n",tot);
	for(int i=1;i<=tot;i++)
	{
		if(ans[i].tpe==1) printf("%lld + %lld\n",ans[i].x,ans[i].y);
		if(ans[i].tpe==2) printf("%lld ^ %lld\n",ans[i].x,ans[i].y);
	}
	return 0;
}