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

思路:

x+km≡y+kn(mod  l)x+km\equiv y+kn (\mod l)

k(m−n)≡y−x(mod  l)k(m-n)\equiv y-x (\mod l)

k(m−n)+kk⋅l=y−xk(m-n)+kk·l=y-x (kk为常数)

然后求出 (m−n)(m-n) 与 ll 的最大公因数,以及k(m−n)+kk⋅l=gcd(m−n,l)k(m-n)+kk·l=gcd(m-n,l) 中的 x,yx,y 的值,然后判断 (y−x)(y-x) 和 gcd(m−n,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
加载中...