poj2215 扩展欧几里得

2019-12-09  本文已影响0人  暖昼氤氲
/*
Time:2019.12.9
Author: Goven
type:扩展欧几里得 
ref:
*/
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;

void ext_gcd(ll a, ll b, ll &x, ll &y, ll &d) {//att: a, b大小无关 
    if (b == 0) {
        d = a;
        x = 1, y = 0;
        return;
    }
    ext_gcd(b, a % b, x, y, d);
    ll tp = x;
    x = y;
    y = tp - a / b * x;
}
 
int main()
{
    ll a, b ,c;
    int k;
    ll x, y, d;
    while (cin >> a >> b >> c >> k) {
        if (!(a || b || c || k)) break;
        ll p = (long long)1 << k;//err1: 使用pow函数会出现重载报错 
        ext_gcd(c, p, x, y, d);
        if ((b - a) % d != 0) cout << "FOREVER" << endl;
        else {
            x = (b - a) / d * x;
            ll m = p / d;
            x = (x % m + m) % m;
            cout << x << endl;
        }
    } 
    return 0;
}
 
上一篇 下一篇

猜你喜欢

热点阅读