题目概述

CF1427E

解题报告

神仙构造题，我又来翻译题解啦QAQ！

如果 $(x,y)=1$ ，根据裴蜀定理，一定能求出两个正整数 $a$ 和 $b$ 使得 $ax-by=1$ ，而且如果 $ax$ 是偶数，那么 $ax\ \mathbb{xor}\ by=1$ ，就可以搞出 $1$ 了（这谁想得到）。

我们想找到一个能够通过加法和异或得到的 $y$ ，使得 $(x,y)=1$ ，考虑往 $x$ 二进制后面加 $0$ 比较方便，我们假设 $x$ 的最高位是 $2^H$ ，那么 $2^Hx\ \mathbb{xor}\ x=2^Hx+x-2^{H+1}$（因为 $x$ 是奇数，所以最后一位一定是 $1$ ，所以减去 $2^{H+1}$ ），而 $(2^Hx+x-2^{H+1},x)=(-2^{H+1},x)=1$ ，所以 $y=2^{H}x\ \mathbb{xor}\ x$ 就是一个合法的 $y$ 。（这tm谁想得到）

用exgcd求出 $a$ 和 $b$ 就好了，用倍增的方式可以 $O(\log_2x)$ 次加法求出 $ax$ 。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=1000000;

int n;LL x,a[maxn+5],b[maxn+5];char tp[maxn+5];

void Add(char op,LL A,LL B) {n++;tp[n]=op;a[n]=A;b[n]=B;}
LL exgcd(LL a,LL b,LL &x,LL &y){
    if (!b) {x=1;y=0;return a;}
    LL r=exgcd(b,a%b,y,x);y-=a/b*x;return r;
}
int main(){
    scanf("%lld",&x);
    LL y=x;for (int i=2;i<=x;i<<=1) Add('+',y,y),y<<=1;
    Add('^',y,x);y^=x;
    LL A,B,T,w,Sx,Sy;exgcd(x,y,A,B);
    if (A<=0) T=-A/y+1,A+=T*y,B-=T*x;
    if (B%2) A+=y,B-=x; B=-B;
    w=x;for (LL i=2;i<=A;i<<=1) Add('+',w,w),w<<=1;
    w=y;for (LL i=2;i<=B;i<<=1) Add('+',w,w),w<<=1;
    for (Sx=0;A;A>>=1,x<<=1)
        if (A&1) {if (Sx) Add('+',Sx,x);Sx+=x;}
    for (Sy=0;B;B>>=1,y<<=1)
        if (B&1) {if (Sy) Add('+',Sy,y);Sy+=y;}
    Add('^',Sx,Sy);
    printf("%d\n",n);for (int i=1;i<=n;i++) printf("%lld %c %lld\n",a[i],tp[i],b[i]);
    return 0;
}