设为首页 - 加入收藏 焦点技术网
热搜:java
当前位置:首页 >

hdu - 2669 - Romantic(扩展欧几里得)

2014-11-02 16:27:00.0 数论  
导读:题意:给出a, b(0= 0。题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2669——>>在找乘法逆元的题目,看到这题简单顺手A了。。#include typedef long long LL;void Gcd(LL a, LL b, LL& d, LL& x, LL& y){ if (!b) { d = a; ...。。。

题意:给出a, b(0= 0。

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2669

——>>在找乘法逆元的题目,看到这题简单顺手A了。。

#include typedef long long LL;void Gcd(LL a, LL b, LL& d, LL& x, LL& y){    if (!b)    {        d = a;        x = 1;        y = 0;    }    else    {        Gcd(b, a % b, d, y, x);        y -= a / b * x;    }}int main(){    int a, b;    LL d = 0, x = 0, y = 0;    while (scanf("%d%d", &a, &b) == 2)    {        Gcd(a, b, d, x, y);        if (d != 1)        {            puts("sorry");        }        else        {            if (x >= 0)            {                printf("%I64d %I64d\n", x, y);            }            else            {                LL t = - x / b;                if (x % b)                {                    ++t;                }                printf("%I64d %I64d\n", x + b * t, y - a * t);            }        }    }    return 0;}


(编辑: SCNU_Jiechao)

网友评论
相关文章