hihocoder 1297.扩展欧几里得

270


题目



点击显/隐题目

小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




题解



模板题


代码


点击显/隐代码
#include <cstdio>
#include <iostream>
using namespace std;

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

// a*x + b*y = 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;
    }
}

// a*x + b*y = 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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论