`

UVA 10104 Euclid Problem

阅读更多

        新手请进:扩展欧几里德入门

/*
*   直接Egcd就得出|x|+|y|最小的解
*   不知道为什么可以这样,我觉得分4种情况讨论的做法更靠谱些
*/
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
#define LL long long
#define M 105
#define inf 0x3fffffff

LL Egcd (LL a, LL b, LL &x, LL &y)
{
    if (b == 0)
    {
        x = 1; y = 0;
        return a;
    }
    LL tp, d;
    d = Egcd (b, a%b, x, y);
    tp = x;
    x = y;
    y = tp-a/b*y;
    return d;
}

int main()
{
    LL a, b, x, y, d;
    while (cin >> a >> b)
    {
        d = Egcd(a, b, x ,y);
        cout << x << ' ' << y << ' ' << d << endl;
    }
    return 0;
}

 

1
1
分享到:
评论

相关推荐

    用户资料界面动画Euclid.zip

    Euclid 实现了用户资料界面动画。 标签:Euclid

    扩展藕几里德算法 EUCLID

    扩展欧几里得算法(Extended Euclidean Algorithm,简称 EUCLID)是求解最大公约数(Greatest Common Divisor, GCD)的经典算法,并且在计算模逆元时有着重要作用。模逆元是指在模m意义下,一个整数a的逆元素b,满足...

    swift-Euclid一个用于创建和操作3D几何体的Swift库

    **Swift-Euclid:3D几何体操作的Swift库** Swift-Euclid 是一个专为Swift编程语言设计的开源库,旨在提供强大的3D几何体创建和操作功能。这个库深受数学家欧几里得(Euclid)的启发,他以其在几何学领域的贡献而...

    Euclid's Game

    ### Euclid's Game知识点解析 #### 一、游戏规则与背景 **Euclid's Game**是一种基于数学原理的游戏,起始于两个不等的正整数(记为M和N,并且M &gt; N)。两名玩家轮流操作。每一轮,一名玩家需要在黑板上写下两个已...

    Robin Hartshorne - Geometry. Euclid and Beyond

    Robin Hartshorne - Geometry. Euclid and Beyond

    Euclid算法及代码

    【欧几里得算法及其应用】 欧几里得算法,又称辗转相除法,是古希腊数学家欧几里得提出的一种求解两个正整数最大公约数(Greatest Common Divisor, GCD)的有效方法。这个算法基于一个非常简单的原理:两个正整数a...

    Euclid高中数学竞赛答案

    ### Euclid高中数学竞赛知识点解析 #### 一、竞赛背景介绍 Euclid数学竞赛是由加拿大数学学会(Canadian Mathematical Society)与数学与计算教育中心(Centre for Education in Mathematics and Computing)联合...

    ,密码学扩展的EUCLID算法求逆元

    - **main函数**:主函数简单地读取输入并调用Euclid函数。 #### 总结与建议 1. **代码风格**:建议使用标准C++库,并遵循现代C++的最佳实践,例如使用`std::vector`代替数组。 2. **代码优化**:可以考虑使用循环...

    Euclid算法

    欧几里得算法的原理在于,GCD(a,b)=GCD(b,r),故称辗转相除。 此cpp可解决: 对任意整数a、b求最大公约数,寻找整数s、t使得a*s+b*t=GCD(a,b)。

    extended-euclid.rar_Euclid_extended euclid_gcd

    《欧几里得扩展算法与最大公约数》 在数学领域,特别是在计算机科学中,欧几里得算法(Euclidean Algorithm)是一个古老而强大的工具,用于计算两个非负整数的最大公约数(Greatest Common Divisor,GCD)。...

    Euclid_Probe:Euclid探针,磁耦合的Z探针底座

    EUCLID探针 高精度,磁耦合Z-Probe,不受床温,床材料或表面处理的影响。 可以通过gcode宏手动或自动部署探针,并利用固件的探针拾取检测方案来确保拾取/释放。 它使用磁铁进行机械耦合和电接触。 连接探针后,Z-...

    euclid algorithm

    euclid 演算法java版

    密码学Euclid算法、扩展Euclid算法、素性检验

    在密码学领域,欧几里得(Euclid)算法、扩展欧几里得(Extended Euclidean)算法以及素性检验是基础且至关重要的数学工具。本文将深入探讨这些概念,并结合C#编程语言来理解它们在实际应用中的实现。 首先,...

    euclid:简约的zsh提示

    欧几里得 极简主义的zsh提示受启发。 特征 由提供 使用图标 灵活的api,易于扩展和自定义 信息密集提示通过谨慎使用颜色和图标 安装 ...$ source euclid/euclid.zsh 您也可以使用您的。 文献资料

    euclid algorithmjava

    **欧几里得算法(Euclid Algorithm)在Java中的实现** 欧几里得算法,又称为辗转相除法,是求解两个正整数最大公约数(Greatest Common Divisor, GCD)的一种高效方法。它基于这样一个原理:对于任何两个正整数a和b...

    Euclid-maste

    "Euclid-maste"似乎是一个项目或软件的名称,它可能与用户界面设计或开发相关。在IT行业中,用户界面(UI)是人与计算机系统交互的桥梁,它包括图形、文字、图标、按钮等元素,旨在使用户能够有效地与系统进行沟通。...

    EUCLID系统的知识获取与机器学习.pdf

    《EUCLID系统的知识获取与机器学习》 在人工智能领域,知识获取与机器学习是实现计算机智能化的关键。现有的智能系统普遍存在着三个主要问题:错误自我纠正能力不足、无法自动获取和发现新知识、推理能力局限于演绎...

    Euclid算法判断互素

    //by史瑞 #include #include #define bool int #define true 1 #define false 0 #define M 2//判断多少个数互素 static long int Number[M]={170,201}; bool JudgePrime(long int Ina,long int Inb){ ...

    euclid:Rust的几何图元(基本线性代数)

    在Rust编程语言中,`euclid`是一个用于处理几何图元和基本线性代数的库,尤其适用于2D图形和布局计算。这个库提供了一组高效且易于使用的数据结构和函数,使得开发者能够在Rust项目中进行精确的几何操作。 `euclid`...

    Euclid:欧几里得文本的基本统计和解析

    在 Project Euclid 中,我们迈出了使用数据科学工具分析古希腊数学的第一步。 这个项目的贡献有两个方面。 首先,我们开发了一个 Web 解析器来自动抓取欧几里德元素并将命题和定义存储在矩阵/对象中,从而使分析...

Global site tag (gtag.js) - Google Analytics