擴(kuò)展歐幾里得專(zhuān)題（一）

2019-11-08 19:30:53

字體：大中小

來(lái)源：轉(zhuǎn)載

供稿：網(wǎng)友

HDU 1222

鏈接： HDU 1222

題解

很容易推出如果n, m互質(zhì)，則不存在安全洞擴(kuò)展歐幾里得求gcd

code

//package adrui;import java.util.*;public class Main{ public static void main(String...args){ Scanner in = new Scanner(System.in); int t = in.nextInt(); while(t-- > 0){ long m = in.nextLong(), n = in.nextLong(); long ans = expgcd(m, n); String tmp = "YES"; if(ans == 1) tmp = "NO"; System.out.PRintln(tmp); } in.close(); } public static long expgcd(long a, long b){ if（b == 0）{ return a; } return expgcd(b, a % b); }}

HDU 1576

鏈接：HDU 1576

題解

推一下式子就成，注意B的系數(shù)要取反

code

//package adrui;import java.util.*;public class Main{ static long c; public static void main(String...args){ Scanner in = new Scanner(System.in); int t = in.nextInt(); while(t-- > 0){ c = in.nextLong(); long[] x = new long[1];/**數(shù)組實(shí)現(xiàn)引用*/ long[] y = new long[1]; long n = in.nextLong(); expgcd(9973, n, x, y); y[0] = -y[0]; long ans = y[0] % 9973; if(ans < 0) ans += 9973; System.out.println(ans); } in.close(); } public static void expgcd(long a, long b, long[] x, long[] y){ if(b == 0){ x[0] = -c; y[0] = 0; return; } expgcd(b, a % b, y, x); y[0] -= a / b * x[0]; }}

HDU 2669

鏈接： HDU 2669

題解

擴(kuò)歐模板，注意要是整數(shù)解，至于x要滿(mǎn)足最小非負(fù)，對(duì)b / gcd(a, b)取模就好了容易得知如果有解， a, b互質(zhì)，所以有解時(shí)直接對(duì)b取模

code

/** *@author : adrui */import static java.lang.System.*;import java.util.*;public class Main{ static boolean f;/**靜態(tài)全局*/ public static void main(String...args){ Scanner in = new Scanner(System.in); while(in.hasNext()){ f = false; int a = in.nextInt(), b = in.nextInt(); int[] x = new int[1]; int[] y = new int[1]; expgcd(a, b, x, y); if(!f) out.println("sorry"); else{ int ans = x[0] % b; if(ans < 0) ans += b;/** b = b / gcd(a, b) */ out.println(ans + " " + (1 - (long)ans * a) / b);/** ans * a 可能會(huì)爆int，用通解也可以*/ } } } public static void expgcd(int a, int b, int[] x, int[] y){ if(b == 0){ if(a == 1) { x[0] = 1; y[0] = 0; f = true;/**有解標(biāo)記*/ } return; } expgcd(b, a % b, y, x); y[0] -= a / b * x[0]; }}

HDU 2504

鏈接： HDU 2504

裸題

code

/** *@author : adrui */import static java.lang.System.*;import java.util.*;public class Main{ public static void main(String...args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); while(n-- > 0){ int a = in.nextInt(), b = in.nextInt(); for(int i = b + b; ; i += b){ if(expgcd(a, i) == b){ out.println(i); break; } } } } public static int expgcd(int a, int b){ if(b == 0){ return a; } return expgcd(b, a % b); }}

上一篇：django實(shí)現(xiàn)自定義權(quán)限控制

下一篇：Groovy閉包參數(shù)