挑战程序竞赛系列（13）：2.6辗转相除法
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434827
挑战程序竞赛系列（13）：2.6辗转相除法
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
AOJ 0005: GCD AND LCM
辗转相除法，著名欧几里德算法。
代码如下：
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str;
long a,b;
while((str=br.readLine()) != null){
a = Long.parseLong(str.substring(0, str.indexOf(" ")));
b = Long.parseLong(str.substring(str.indexOf(" ")+1, str.length()));
System.out.println(gcd(a, b) + " " + lcm(a,b));
}
}
private static long gcd(long a, long b){
if (b == 0) return a;
return gcd(b, a % b);
}
private static long lcm(long a, long b) {
return a * b / gcd(a, b);
}POJ 2429: GCD & LCM Inverse
这道题是我学算法以来，程序代码最长的一次，思路是相当简单的，但为了避免TLE，算法优化不简单。
思路：
- 取lcm/gcd，如3，60，得到20，在20中找到所有因子，如：2*10，4*5，取因子之和最小的两个因子。
- 输出 gcd * f1 和 gcd *f2
非常暴力的做法，求因子可以使用试除法，把每个小于num的因子扫描一遍，但时间复杂度为O(n)O(n)，当num非常大时，这种时间开销受不了。
两种经典算法，Miller-Rabin素数测试和Pollard_Rho_因数分解算法实现，高级高级，理解起来费劲，尤其是理论推导它为何能够奏效。
学完两种算法后，发现Pollard_Rho也能检测素数，但速度要比Miller-Rabin慢，所以还是用Pollard_Rho做因数分解吧。
代码如下：
static class Pair{
long fir;
long sec;
}
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
while (true){
long gcd = in.nextLong();
long lcm = in.nextLong();
if (gcd == 0 && lcm == 0) break;
map = new HashMap<>();
Pair p = solve(gcd, lcm);
System.out.println(p.fir * gcd + " " + p.sec * gcd);
}
}
private static Pair solve(long a, long b){
long c = b / a;
find(c, 26632);
int size = 0;
for (long key : map.keySet()){
size += map.get(key);
}
long[] factor = new long[size];
int k = 0;
for (long key : map.keySet()){
int cnt = map.get(key);
while ((cnt--) != 0){
factor[k++] = key;
}
}
int mask = 1 << size;
long min = Integer.MAX_VALUE;
Pair p = new Pair();
for (int i = mask - 1; i>= 0; --i){
long f1 = 1;
for (int j = 0, m = 1; j < size; ++j, m <<= 1){
if ((i & m) != 0){
f1 *= factor[j];
}
}
long f2 = c / f1;
if (f1 < f2 && (f1 + f2) < min){
p.fir = f1;
p.sec = f2;
min = f1 + f2;
}
}
return p;
}
public static long quickMul(long a, long b, long mod){
long ans = 0;
while (b != 0){
if ((b & 1) != 0){
b--;
ans = (ans + a) % mod;
}
b >>= 1;
a = (a + a) % mod;
}
return ans;
}
public static long quickPow(long a, long b, long mod){
long ans = 1;
while (b != 0){
if ((b & 1) != 0){
b--;
ans = quickMul(ans, a, mod);
}
b >>= 1;
a = quickMul(a, a, mod);
}
return ans;
}
public static boolean witness(long a, long n){
long tem = n - 1;
int j = 0;
while (tem % 2 == 0){
tem /= 2;
j++;
}
long x = quickPow(a, tem, n);
if (x == 1 || x == n - 1) return true;
while ((j--) != 0){
x = quickMul(x, x, n);
if (x == n - 1) return true;
}
return false;
}
private static long random(long n){
return Math.abs(new Random().nextLong() % (n + 1));
}
public static boolean millerRabin(long n, int times){
if (n == 2) return true;
if (n < 2 || n % 2 == 0) return false;
for (int i = 0; i < times; ++i){
long a = random(n - 2) + 1;
if (!witness(a, n)) return false;
}
return true;
}
public static long gcd(long a, long b){
if (b == 0) return a;
else return gcd(b, a % b);
}
public static long pollardRho(long n, long c){
long x, y, d, i = 1, k = 2;
x = random(n - 1) + 1; //[1,n]
y = x;
while (true){
i++;
x = (quickMul(x, x, n) + c) % n;
d = gcd(y - x, n);
if (1 < d && d < n) return d;
if (y == x) return n;
if (i == k){
y = x;
k <<= 1;
}
}
}
static Map<Long, Integer> map;
public static void find(long n, long c){
if (n == 1) return;
if (millerRabin(n, 20)){
//map.put(n, map.getOrDefault(n, 0) + 1);
if (!map.containsKey(n)) map.put(n, 0);
map.put(n, map.get(n) + 1);
return;
}
long p = n;
long k = c;
while (p >= n) p = pollardRho(p, c--);
find(p, k);
find(n / p, k);
}测试了一些基础样例，能通过，但不知道为什么在OJ上提交时，Runtime Error，看不到测试数据，有点蛋疼。
- Miller-Rabin素数判定可以参考博文：http://blog.csdn.net/maxichu/article/details/45458569
- 因数分解Pollard_rho 算法可以参考博文：http://blog.csdn.net/maxichu/article/details/45459533
这两篇文章把整个算法的核心讲清楚了，主要用到了费马小定理，以及一些素数合数的基本性质。
在这里，讲一些帮助理解算法和解决问题的感悟吧，自己能够在适当时候想起来就算没白分析。
快速乘法&&快速幂
我并不知道乘法变成加法的形式，到底是代码层面的优化要快，还是操作系统层面做乘法快，但此处之所以提出快速乘法是为了解决数long * long的溢出问题，一旦溢出%n的答案就不再正确，所以与其在相乘后求mod，还不如在计算过程当中不断取mod，避免溢出问题。
long a ，long b， long n，求：(a * b) % mod
思路很简单，把乘法看成加法即可，但怎么讲究效率，且有规律的办法是每次把问题规模缩减一半，所以快速取模乘法的时间复杂度为O(logn)O(\log n)
唉，其实用到的是二进制换十进制的计算法则，但没想到这种法则，能够让乘法从O(n)O(n)提高到O(logn)O(\log n)，神奇。
eg:
a = a, b = 13
13 12 6 3 2 1
a 2a 4a 5a 8a 13a
可能不够直观，但上述确实算法的执行流程，起初还纠结怎么来的，其实可以把13用二进制表示：
1101
所以，当遇到第一位为1时，ans += a;与此同时左移一位，且a = a + a,在第二位时，a = 2a
0110
再进行左移，a = 4a
0011
此时，第一位为1，ans += 4a, ans = 5a;接着左移，且a = 8a
0001
第一位为1，ans += 8a, ans = 13a,循环结束。
一句话可以总结，实际就是：
1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0 = 13刚开始真没意识到就是这样一个二进制转十进制的计算过程，呵呵，初中学过，写代码却不知道。从代码结构来看，复杂度很好分析，因为每次除2，类似于递归，深度为O(logn)O(\log n)，代码如下：
public static long quickMul(long a, long b, long mod){
long ans = 0;
while (b != 0){
if ((b & 1) != 0){
b--;
ans = (ans + a) % mod;
}
b >>= 1;
a = (a + a) % mod;
}
return ans;
}还需要证明一件事：a * a mod n = (a mod n) * (a mod n) mod n或者更一般地，a * b mod n = (a mod n) * (b mod n) mod n，很容易，知道这样一个事实即可：
⌊xn−k⌋=⌊xn⌋−k
\lfloor \frac{x}{n} - k \rfloor = \lfloor \frac{x}{n} \rfloor - k
k是整数，所以一个数在楼层之间浮动，并不影响它与地板的相对位置，很显然的一个结论，利用它就可以证明上述取模的正确性了。
继续快速幂，把乘法看成加法，自然地可以把指数看成乘法，用到的思路依旧是二进制计算表达式，这样就容易理解了。
代码如下：
public static long quickPow(long a, long b, long mod){
long ans = 1;
while (b != 0){
if ((b & 1) != 0){
b--;
ans = quickMul(ans, a, mod);
}
b >>= 1;
a = quickMul(a, a, mod);
}
return ans;
}特别提一句b–，可以省略，因为整数取下底奇数–的答案和直接奇数一个效果。
POJ 1930: Dead Fraction
这道题很是无语。。。0.22222…. 可以看成：
2/9
22/99
...
22222/99999
但这些情况，都是最基础的2/9
0.12368...
有多种情况：
0.12 + 0.00368368...
0.123 + 0.0006868...
所以可以有：
12/100 + 368/99900
答案呼之欲出，题目还要求虽小的分母，所以遍历各种情况，取分母最小即可。代码如下：
static class Fraction{
long fz;
long fm;
public Fraction(long fz, long fm){
long d = gcd(fz, fm);
fz /= d;
fm /= d;
this.fz = fz;
this.fm = fm;
}
public Fraction add(Fraction that){
long a1 = this.fz;
long b1 = this.fm;
long a2 = that.fz;
long b2 = that.fm;
return new Fraction(a1 * b2 + b1 * a2, b1 * b2);
}
public long gcd(long a, long b){
if (b == 0) return a;
else return gcd(b, a % b);
}
@Override
public String toString() {
return fz + "/" + fm;
}
}
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
while (true){
String str = in.next();
if (str.equals("0")) break;
str = str.substring(2, str.length() - 3);
char[] digit = str.toCharArray();
if (digit.length == 1 && digit[0] == '0'){
System.out.println("0/1");
continue;
}
Fraction min = new Fraction(1, Long.MAX_VALUE);
for (int i = 0; i < digit.length - 1; ++i){
long a1 = 0;
long b1 = 1;
for (int j = 0; j <= i; ++j){
a1 = a1 * 10 + digit[j] - '0';
b1 = b1 * 10;
}
Fraction f1 = new Fraction(a1, b1);
long a2 = 0;
long b2 = 0;
for (int j = i + 1; j < digit.length; ++j){
a2 = a2 * 10 + digit[j] - '0';
b2 = b2 * 10 + 9;
}
Fraction f2 = new Fraction(a2, b2 * b1);
Fraction f3 = f1.add(f2);
if (f3.fm < min.fm){
min.fz = f3.fz;
min.fm = f3.fm;
}
}
long a1 = 0;
long b1 = 0;
for (int i = 0; i < digit.length; ++i){
a1 = a1 * 10 + digit[i] - '0';
b1 = b1 * 10 + 9;
}
Fraction f3 = new Fraction(a1, b1);
if (f3.fm < min.fm){
min.fz = f3.fz;
min.fm = f3.fm;
}
System.out.println(min.toString());
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年06月20日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录