http://poj.org/problem?id=1061
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1657
两题一模一样,只是无解时输出情况不同
首先由题意有【x+ms与y+ns建立等价关系,设次数为s】:
x+ms ≡ (y+ns)(mol L)
->(x+ms)%L = (y+ns)%L
->((x+ms) - (y+ns))%L = 0
->(x+ms) - (y+ns) = k*L
化简得:
k*L + (n-m)*s = x-y
令a = L,b = n-m,n = x-y得
ak + bs = n;[其中k,s为未知数,形如ax + by = n
Egcd解析:(Egcd是用来解ax+by=gcd(a,b)的(a,b是常数))
解方程步骤:
①:令d = gcd(a, b)
②:若n%d != 0,则无解
③:方程两边同时除以d ,得到a'k + b's = n'
④:用扩展欧几里德Egcd求出a'k + b's = 1的解s
⑤:得到的[s*n']就是方程的一组解
⑥:得到最小非负整数解,模a+a模a【求b的模a,求a的模b, 为什么?请读者自己思考】
#include <iostream>
#include <algorithm>
#include <string>
//#include <map>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
//#include <ctime>
#include <ctype.h>
using namespace std;
#define LL long long
#define inf 0x3fffffff
LL gcd (LL a, LL b)
{
return b ? gcd (b, a%b) : a;
}
void Egcd (LL a, LL b, LL &x, LL &y)
{
if (b == 0)
{
x = 1, y = 0;
return ;
}
Egcd (b, a%b, x, y);
LL tp = x;
x = y;
y = tp - a/b*y;
}
int main()
{
LL xx, yy, a, b, x, y, L, n, M, N, d;
while (~scanf ("%lld%lld%lld%lld%lld", &xx, &yy, &M, &N, &L))
{
a = L;
b = N - M;
n = xx - yy;
d = gcd (a, b);
if (n % d != 0)
{
puts ("Impossible");
continue;
}
a /= d;
b /= d;
n /= d;
Egcd (a, b, x, y);
y *= n;
if (a < 0) a = -a; //周期是正的
y = (y % a + a) % a;
printf ("%lld\n", y);
}
return 0;
}
- 大小: 13.1 KB
分享到:
相关推荐
欧几里德算法和扩展欧几里德算法,经典算法系列
用的是扩展欧几里德算法 可是参考网址http://blog.csdn.net/Fioman/archive/2008/05/18/2455698.aspx 上的算法 青蛙的约会 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 36755 Accepted: 4913 ...
欧几里德算法和扩展欧几里德算法.doc
欧几里德算法和扩展欧几里德算法--透彻理解 模P乘法逆元 对于整数a、p,如果存在整数b,满足a×b mod p =1,则说,b是a的模p乘法逆元。
就是扩展欧几里德算法
扩展欧几里德定理
RSA扩展欧几里德算法算例,说明RSA密钥计算过程.
扩展欧几里德算法 欧几里德算法 代码 不可多得的资源
acm 扩展欧几里德算法与中国剩余定理ppt教程 acmer教程系列 acm 扩展欧几里德算法与中国剩余定理ppt教程 acmer教程系列 很详细的讲解哦!
欧几里德算法和扩展欧几里德算法。用C和C++实现。.zip
扩展欧几里德问题,总结的课件,基本的内容都有了,由欧几里德引申到扩展欧几里德问题
实现扩展欧几里得算法的代码,很简单,能够成功运行。
个人初学C++,小试身手,供参考,网上有很多,我的是原创,但不是最好的
Matlab,扩展欧几里德算法,求模b条件下,a的乘法逆元,函数Eulid.m,直接调用传入参数就可以用,含参数使用注释。
两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们 很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为 止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的...
扩展欧几里得算法求逆元
欧几里德算法 欧几里德算法 欧几里德算法 欧几里德算法欧几里德算法欧几里德算法欧几里德算法欧几里德算法欧几里德算法欧几里德算法欧几里德算法
包含两个功能。 one 函数计算两个多项式 a(x) 和 b(x) 在 GF(2^m) 上... 另一个函数执行扩展的欧几里德算法,其中除了 a(x) 和 b(x) 的 gcd 之外,还计算了两个多项式 u(x) 和 v(x),使得 gcd = u(x)a(x) + v(x)b(x)。
欧几里德算法和扩展.doc
乘法逆元算法,扩展欧几里德,自己实现的,不过借鉴了网上的发达发达省份打发打发