杭电2669拓展欧几里得

简介: 给a,b求Xa Yb = 1.如果没有则输出sorry。

给a,b求Xa Yb = 1.如果没有则输出sorry。


可以通过拓展欧几里得指导Xa Yb = gcd(a,b).


不言而喻要判断gcd(a,b)是否等于1.如果不等于1,那么就是sorry。如果等于一,那么还不能让x小于0,要对x,y进行加减操作满足x>0;拓展欧几里得是通过递归从下往上进行运算。


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
/*
 * 拓展欧几里得
 */
public class hdu2669 {
 static long x=0;static long y=0;
  public static void main(String[] args) throws IOException {
    // TODO 自动生成的方法存根
    StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    while(in.nextToken()!=StreamTokenizer.TT_EOF)
    {
      long a=(long)in.nval;
      in.nextToken();
      long b=(long)in.nval;
      long q=tgcd(a,b);
      if(1%q!=0) {out.println("sorry");}//gcd要和要求相等(这里等于1)
      else {
        while(x<=0){//x*a y*b=1 要求x>0这样并且要求x最小,那么这样操作就相当于 ab-ab操作。刚开始还没明白
          x =b;
          y-=a;
        }
        out.println(x " " y);}//
      out.flush();
    }   
  }
  static long tgcd(long a,long b)
  {
    if(b==0) {x=1;y=0;return a;}
    long ans=tgcd(b,a%b);
    long team=x;
    x=y;
    y=team-a/b*y;
    return ans;
  }
}
目录
相关文章
|
6月前
杭电计算几何
杭电计算几何
40 0
|
6月前
|
算法 C++
小唐蓝桥的做题心得
小唐蓝桥的做题心得
|
存储 人工智能 JavaScript
【寒假每日一题】AcWing 4510. 寻宝!大冒险!
目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解
135 0
|
存储 人工智能 BI
【蓝桥杯集训·每日一题】AcWing 1249. 亲戚
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 并查集
90 0
|
存储 机器学习/深度学习 算法
蓝桥杯十大常见天阶功法——虫之呼吸.贰之型.二分
蓝桥杯十大常见天阶功法——虫之呼吸.贰之型.二分
273 0
蓝桥杯十大常见天阶功法——虫之呼吸.贰之型.二分
|
测试技术
杭电1232 畅通工程
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?
150 0
|
算法
每日一题之亲戚
大家好,我是泡泡,给大家带来每日一题的目的是为了更好的练习算法,我们的每日一题这个月进度是数据结构,让大家练到各种各样的数据结构题目,熟悉数据结构的增删改查,一年以后,蜕变成为一个不一样的自己!
148 0
HDU-2897,邂逅明下(巴什博弈)
HDU-2897,邂逅明下(巴什博弈)
|
机器学习/深度学习 算法
[leetcode/lintcode 题解] 算法面试真题详解:流浪剑客斯温
[leetcode/lintcode 题解] 算法面试真题详解:流浪剑客斯温
[leetcode/lintcode 题解] 算法面试真题详解:流浪剑客斯温