杭电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++
【PTA】​L1-079 天梯赛的善良​ (C++)
【PTA】​L1-079 天梯赛的善良​ (C++)
108 0
【PTA】​L1-079 天梯赛的善良​ (C++)
|
6月前
|
C++
【PTA】L1-035 情人节(C++)
【PTA】L1-035 情人节(C++)
62 0
【PTA】L1-035 情人节(C++)
|
6月前
牛客小bai月赛39 F 孤独(dp)
牛客小bai月赛39 F 孤独(dp)
41 0
|
测试技术
杭电1232 畅通工程
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?
150 0
HDU-2897,邂逅明下(巴什博弈)
HDU-2897,邂逅明下(巴什博弈)
七月观荷 - 江湖一剑客
致敬普吕多姆和阿多尼斯 也如这清晨的薄雾,如它温暖的丝线—— 我的诗歌只为你灵魂的黑夜而作 一经被人窥破,便要苍白失色 万物静默如斯,唯有孤独,恒常如新 世间绝美的东西一定是转瞬即逝的——正是因为这样的转瞬即逝才造就了绝美。
1183 0
|
程序员
拾叶集 - 江湖一剑客
夜空如此,安静,星光闪闪。 你是风,你是风中之风。 你是来自,宇宙深处的幽蓝。 你这个可爱的人儿 像一只小猫咪 在深夜里 化成了窗外的一缕清风 拥入胸怀 归 心归故乡 想象行走在 乡间恬静小路上 让那些疲惫的梦 都随风飞散吧! 不去想那些世俗 人来人往...
1227 0
晨曦 - 江湖一剑客
别问我靠什么谋生 我不感兴趣 我内心真正渴望的是什么 我是否有勇气 去追逐心中的渴望 别问我年龄 我不感兴趣 草木一秋 人生百年 蜉蝣掘阅 麻衣如雪 我只想知道 我是否愿意去用生命去冒险 为了爱 为了梦想 绽放生命芳华 当走到生命的终点 当所有的一切都...
1339 0