HDU2669 Romantic

文章目录

1. 1. 题意
2. 2. 分析

原题

题意

求满足Xa + Yb = 1的最小的非负正整数x，同时输出x和对应的y。

分析

裸题,判定一下gcd(a,b)是不是等于1，然后直接处理x的非负就行了。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll gcd(ll a,ll b){
    return b==0?a:gcd(b,a%b);
}
void exgcd(ll a,ll b,ll& x,ll& y){
    if(b==0){
        x=1;y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    ll temp=x;
    x=y;
    y=temp-a/b*y;
    return;
}
int main(){

    ll a,b,x,y;
    while(scanf("%I64d%I64d",&a,&b)!=EOF){
        if(gcd(a,b)!=1){
            printf("sorry\n");
        }
        else{
            exgcd(a,b,x,y);
            if(x<0){
                x+=b;
                y-=a;
            }
            printf("%I64d %I64d\n",x,y);
        }
    }
    return 0;
}