小Y的数论题

wjh15101051's space

卧薪尝胆，厚积薄发。

小Y的数论题

Date: Sun Aug 26 09:53:07 CST 2018

In Category: NoCategory

Description：

已知 $m,a,b,c$ ，构造 $x,y,z$ 使得 $x^a+y^b=z^c(mod\ m)$

$1\le m,a,b,c\le 10^9,1\le t \le 100000$

Solution：

只要构造一组就行了。

设 $x=2^{bk},y=2^{ak}$ ，则左边 $=2^{abk+1}$ 。

于是要构造 $z^c=2^{abk+1}$ ，设 $z=2^l$ ，于是 $2^{lc}=2^{abk+1}$ ，即 $lc=abk+1$ ， $l,k$ 必须是非负整数。

于是扩欧解出来即可。

不过如果 $m=2^w$ ，即 $m$ 是 $2$ 的幂，那么特判。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

typedef long long ll;

ll m,a,b,c;

ll power(ll a,ll b)

{

	ll res = 1;

	while(b > 0)

	{

		if(b & 1)res = res * a % m;

		a = a * a % m;

		b = b >> 1;

	}

	return res;

}

void exgcd(ll a,ll b,ll &x,ll &y)

{

	if(b == 0)

	{

		x = 1;y = 0;

		return;

	}

	exgcd(b,a % b,x,y);

	ll k = x;

	x = y;y = k - a / b * y;

	return;

}

void work()

{

	scanf("%lld%lld%lld%lld",&m,&a,&b,&c);

	ll t = log2(m);

	ll x,y,z;

	if(pow(2,t) == m)

	{

		x = 1;y = 1;z = 1;

		if(a > 1)x = m / 2;

		else if(b > 1)y = m / 2;

		else if(c > 1){x = m / 2;y = m / 2;z = m / 2;}

		else {x = y = 1;z = 2;}

		printf("%lld %lld %lld\n",x,y,z);

		return;

	}

	ll l,k;

	exgcd(c,a * b,l,k);k = -k;

	while(l < 0 || k < 0){l += a * b;k += c;}

	x = power(2,b * k);y = power(2,a * k);z = power(2,l);

	printf("%lld %lld %lld\n",x,y,z);

	return;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}

In tag: 数学-扩展欧几里得

wjh15101051