拓展欧几里得算法模板

野性酷女 2022-08-03 13:49 124阅读 0赞

暂时还不明白，留着以后慢慢明白。

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline ll in()
    {
        ll res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    ll e_gcd(ll a,ll b,ll &x,ll &y)
    {
        if(b==0)
        {
            x=1;
            y=0;
            return a;
        }
        ll ans=e_gcd(b,a%b,x,y);
        ll tmp=x;
        x=y;
        y=tmp-a/b*y;
        return ans;
    }
    ll cal(ll a,ll b,ll c)
    {
        ll x,y;
        ll gcd=e_gcd(a,b,x,y);
        if(c%gcd!=0)return -1;
        x*=c/gcd;
        b/=gcd;
        if(b<0)b=-b;
        ll ans=x%b;
        if(ans<=0)ans+=b;
        return ans;
    }
    
    int main()
    {
        ll a,b;
        while(~scanf("%I64d%I64d",&a,&b))
        {
    
            ll ans=cal(a,b,1);
            if(ans==-1)puts("sorry");
            else printf("%I64d %I64d\n",ans,(1-ans*a)/b);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，124人围观）

还没有评论，来说两句吧...

相关阅读

相关欧几里得算法

一.自然语言描述：计算两个非负整数p和q的最大公约数：若q是0，则最大公约数为p。否则，将p除以q得到余数r，p和q的最大公约数即为q和r的最大公约数。二.Jav

╰+哭是因爲堅強的太久メ/ 2024年03月23日 17:45/ 0 赞/ 65 阅读

相关欧几里得算法

欧几里得算法中，计算 x, y 的最大公约数的方法是辗转相除，例如： gcd (26, 15) 26 % 15 = 1 ... 11 15 % 11 = 1 ... 4

秒速五厘米/ 2022年10月01日 13:46/ 0 赞/ 219 阅读

相关欧几里得和扩展欧几里得算法

（一）欧几里得算法又称辗转相除法，是求解两个数的最大公约数的算法，基本定义为：设 a=qb+r，其中a，b，q，r都是整数，则：gcd（a，b）= gcd（b，r）利用

ゞ浴缸里的玫瑰/ 2022年08月21日 03:20/ 0 赞/ 252 阅读

相关拓展欧几里得算法模板

暂时还不明白，留着以后慢慢明白。 include<map> include<vector> include<cstdio> includ

野性酷女/ 2022年08月03日 13:49/ 0 赞/ 125 阅读

相关扩展欧几里得算法

问题描述：求解二元一次方程ax+by=c。问题分析：上述的二元一次方程可以用同余方程来进行描述：ax≡cmod(b) 两个问题可以进行转换，但是都可以用扩展的欧几

心已赠人/ 2022年06月15日 10:00/ 0 赞/ 248 阅读

相关算法——欧几里得算法

计算二个非负整数p和q的最大公约数。若q=0，则最大的公约数为p，否则，将p/q得到的余数r，p和q的最大公约数即为q和r的最大公约数 pubulic static int

素颜马尾好姑娘i/ 2022年04月03日 04:48/ 0 赞/ 233 阅读

相关数论杂谈——欧几里得算法及扩展欧几里得

数学是oi的重要基础，所以说数论在oi中占据了非常重要的地位，因此，学好数学，对于一个oier来说也是非常重要的。 oi中的数学，其实也就和数竞并没有什么区别。欧几里得法

落日映苍穹つ/ 2021年12月23日 23:55/ 0 赞/ 356 阅读

相关欧几里得算法和扩展欧几里得算法数论基础

　　这两个算法可以说是OI里数学模块最重要的基础了（如果位运算不算数学的话）。一.欧几里得算法（Euclidean Algorithm）　　模板水题：[LOJ P121

r囧r小猫/ 2021年12月12日 07:19/ 0 赞/ 325 阅读

相关扩展欧几里得算法

下面直接使用简称exgcd就好。先引入紫书上的一个经典问题，求直线方程ax+by+c=0的所有整数解。我们先来看一个简单的，求ax+by=gcd(a,b)的一组整数解。

今天药忘吃喽~/ 2021年09月29日 21:02/ 0 赞/ 410 阅读

相关欧几里得算法

一代码 package Euclid; / Copyright (C), 2020-2020, XXX有限公司 Fi

红太狼/ 2021年07月24日 16:01/ 0 赞/ 420 阅读