D. ConstructOR

比较奇怪的数学题叭...

要求一个$xx$使之和$a,ba,b$或后都能整除$dd$.

首先$a,ba,b$中$mi{n}_{sufzero}min\_\{sufzero\}$假如少于$dd$的$mi{n}_{sufzero}min\_\{sufzero\}$这种一定是不存在酱紫的$xx$的.

不妨假设$dd$后面有$kk$个$00$,$d^{\mathrm{\prime }}d\text{'}$为去掉那$kk$个$00$的数.那么我$a,ba,b$同理也需要去掉$kk$个$00$.

之后我们用$x\{x\}$把$a,b\{a,b\}$前面全部变成$1\{1\}$.

假设$n=2^{30-k}n=2^\{30-k\}$.

那么$a,ba,b$就可以合在一起考虑了,不妨设值为$y=p\ast n+n-1y=p*n+n-1$,要求$yy$%$d^{\mathrm{\prime }}d\text{'}$为$00$.

$y^{\mathrm{\prime }}=p\ast n+ny\text{'}=p*n+n$.就是相当于$y^{\mathrm{\prime }}y\text{'}$%$d^{\mathrm{\prime }}d\text{'}$等于$11$.

貌似用$exgcdexgcd$就好了.

而且方程是一定有解的,因为$d^{\mathrm{\prime }}d\text{'}$是奇数,$AA$是只含质因子$22$的偶数,$gcdgcd$一定是$11$.

所以好神奇诶?

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N=2e5+5;
const int M=2;

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0){x=1;y=0;return a;}
    ll d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

void run()
{
	ll a,b,d;
	scanf("%lld%lld%lld",&a,&b,&d);
	int sufa=0,sufb=0,sufd=0;
	while(a%2==0)	a/=2,sufa++;
	while(b%2==0)	b/=2,sufb++;
	while(d%2==0)	d/=2,sufd++;
	if(min(sufa,sufb)<sufd)
	{
		puts("-1");
		return;
	}
	ll A=1,ss=1;
	for(int i=1;i<=30-sufd;i++)	A=A*2;
	for(int i=1;i<=30;i++)	ss=ss*2; 
	ll C=(d);
	ll B=((1-A)%d+d)%d;
	if(B%__gcd(A,C)!=0)
	{
		puts("-1");
		return ;
	}
	ll x,y;
	ll D=exgcd(A,C,x,y);
	ll s=C/D;
	x=B/D*x;
	x=(x%s+s)%s;
	x=x*ss;
	ss=1;
	for(int i=1;i<=30;i++)
	{
		if(i>sufd)	x+=ss;
		ss=ss*2;
	}
	printf("%lld\n",x);
}

int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		run();
	}
	return 0;
}