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;
}

 

全部评论

相关推荐

不愿透露姓名的神秘牛友
11-01 21:29
点赞 评论 收藏
分享
codemelo:终面的一般都是很高级别的,肯定难约😋
点赞 评论 收藏
分享
09-29 11:19
门头沟学院 Java
点赞 评论 收藏
分享
身边的人都在收获,我却还在原地踏步,到底该怎么办啊!每次看到他们的好消息,我都想放弃,心里不停地问自己:到底该怎么才能找到一份工作呢?这种无力感让我想要彻底摆烂,真的很想知道,别人是怎么做到的。有没有人分享一下经历呢?我想学习一下啊走出这样的日子。
鼗:秋招其实是运气>实力的一场竞技游戏,除非实力很强(学历和技术)。大多数人都是半斤八两,看面试官和HR以及简历被曝光的概率罢了,有些时候你可能运气差一点或者说面试官不太友好也或者说你确实准备的不够好之类的,这些都是可能发生的事情。我觉得能做的事情是不比较、不气馁、在面试前多看一点面试的时间冷静一点自信一点,大大方方面试,给自己多一点时间去求职。我这样说不是站着说话不腰疼,我是想说你的offer还在路上,你也值得在这些困难之后得到你较为理想的offer,请你继续加油,保持乐观,积极打败你现在的困难
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务