{% 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
模板题
{% 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 %}此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。