POJ - 1061 扩展欧几里德算法+求最小正整数解

//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#pragma GCC optimize(2)
#include <algorithm>
#include <iostream>
#include<sstream>
#include<iterator>
#include<cstring>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>

using namespace std;

typedef double dou;
typedef long long ll;

#define M 100005
#define inf 0x3f3f3f3f
#define mod 1000000007  
#define left k<<1
#define right k<<1|1
#define W(a) while(a)  
#define ms(a,b) memset(a,b,sizeof(a))

ll gcd_pro(ll A, ll B, ll &x, ll &y) {
    if (B == 0) {
        x = 1, y = 0;
        return A;
    }
    ll ans = gcd_pro(B, A % B, y, x);
    y = y - (A / B) * x;
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);

    ll gcd;
    ll x, y;
    ll st_x, st_y, m, n, L;

    cin >> st_x >> st_y >> m >> n >> L;

    gcd = gcd_pro(m - n, L, x, y);

    if ((st_y - st_x) % gcd != 0) {
        cout << "Impossible" << endl;
    }
    else {
        x = x * (st_y - st_x) / gcd;
        L /= gcd;
        x %= L;
        if (x < 0) {
            if (L < 0)L = -L;
            x += L;
        }
        cout << x << endl;
    }

    return 0;
}

 

全部评论

相关推荐

一个菜鸡罢了:哥们,感觉你的简历还是有点问题的,我提几点建议,看看能不能提供一点帮助 1. ”新余学院“别加粗,课程不清楚是否有必要写,感觉版面不如拿来写一下做过的事情,教育经历是你的弱势就尽量少写 2. “干部及社团经历”和“自我评价”删掉 3. 论文后面的“录用”和“小修”啥的都删掉,默认全录用,问了再说,反正小修毕业前肯定能发出来 4. 工作经验和研究成果没有体现你的个人贡献,着重包装一下个人贡献
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务