20分数论小白求教
查看原帖
20分数论小白求教
288716
lzqy_楼主2020/7/27 16:09

思路:

x+kmy+kn(modl)x+km\equiv y+kn (\mod l)

k(mn)yx(modl)k(m-n)\equiv y-x (\mod l)

k(mn)+kkl=yxk(m-n)+kk·l=y-x (kk为常数)

然后求出 (mn)(m-n)ll 的最大公因数,以及k(mn)+kkl=gcd(mn,l)k(m-n)+kk·l=gcd(m-n,l) 中的 x,yx,y 的值,然后判断 (yx)(y-x)gcd(mn,l)gcd(m-n,l) 是否有倍数关系,有则输出 kk,否则输出“Impossible”

code:

#include<bits/stdc++.h>
using namespace std;
struct p
{
	long long x,y,GCD;
};
p exgcd(long long a,long long b)
{
	if(b==0)
	{
		p M;
		M.x=1,M.y=0,M.GCD=a;
		return M;
	}
	p M=exgcd(b,a%b);
	p ans;
	ans.x=M.y,ans.y=M.x-a/b*M.y,ans.GCD=M.GCD;
	return ans;
}
int main()
{
	long long x,y,m,n,l;
	cin>>x>>y>>m>>n>>l;
	long long a=y-x,b=m-n;
	b=(b%l+l)%l;
	a=(a%l+l)%l;
    p yuhaohanhan=exgcd(b,l);
    if(yuhaohanhan.GCD%a==0||a%yuhaohanhan.GCD==0)
    cout<<(yuhaohanhan.x%l+l)%l;
    else
    cout<<"Impossible";
    return 0;
}

求助qwq

2020/7/27 16:09
加载中...