题目

{% fold 点击显/隐题目 %}

小Hi和小Ho周末在公园溜达。公园有一堆围成环形的石板,小Hi和小Ho分别站在不同的石板上。已知石板总共有m块,编号为 0..m-1,小Hi一开始站在s1号石板上,小Ho一开始站在s2号石板上。 小Hi:小Ho,你说我们俩如果从现在开始按照固定的间隔数同时同向移动,我们会不会在某个时间点站在同一块石板上呢? 小Ho:我觉得可能吧,你每次移动v1块,我移动v2块,我们看能不能遇上好了。 小Hi:好啊,那我们试试呗。 一个小时过去了,然而小Hi和小Ho还是没有一次站在同一块石板上。 小Ho:不行了,这样走下去不知道什么时候才汇合。小Hi,你有什么办法算算具体要多久才能汇合么? 小Hi:让我想想啊。。 提示:扩展欧几里德
第1行:每行5个整数s1,s2,v1,v2,m,0≤v1,v2≤m≤1,000,000,000。0≤s1,s2<m 中间过程可能很大,最好使用64位整型
第1行:每行1个整数,表示解,若该组数据无解则输出-1
0 1 1 2 6
5
{% endfold %}

题解

模板题

代码

{% fold 点击显/隐代码 %}```cpp 扩展欧几里得 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
#include
#include
using namespace std;

// gcd(a,b)
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }

// ax + by = gcd(a,b)
long long ex_gcd(long long a, long long b, long long &x, long long &y) {
if (!b) {
x = 1;
y = 0;
return a;
} else {
long long d = ex_gcd(b, a % b, y, x);
y -= x * (a / b);
return d;
}
}

// ax + by = c
bool solve(long long a, long long &x, long long b, long long &y, long long c,
long long minx) {
long long d = ex_gcd(a, b, x, y);
if (c % d)
return false;

long long m = b / d;
if (m < 0)
    m = -m;
x *= c / d;
x = (x % m + m) % m;
y = (c - a * x) / b;
return true;

}

int main() {
cin.tie(0);
cin.sync_with_stdio(false);
long long s1, s2, v1, v2, m;
while (cin >> s1 >> s2 >> v1 >> v2 >> m) {
long long x, y;
if (solve(v1 - v2, x, m, y, s2 - s1, 0))
cout << x << endl;
else
cout << "-1" << endl;
}
return 0;
}

{% endfold %}