Big Number

 題目鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=1722

　　　　——每天線上，歡迎留言談論。

題目大意：

 給你兩個數 n1,n2 。

 然後你有一塊蛋糕，提前切好，使得不管來 n1 還是 n2 個人都能夠當場平均分配。

 求 “提前切好” 的最小蛋糕塊數。

知識點：

（請無視）公式：N = a + b + gcd(a, b) ；

思路：

（勿無視）先份成p塊，然後再拼到一起，再從原來開始的地方，將蛋糕再分成q份，中間肯定會出現完全重合的塊數為k，則此是需要分的塊數就是 p + q - k 。

 PS. K = gcd(a, b) 。

Java AC代碼：

 1 import java.util.Scanner;
 2 import java.math.*;
 3 public class Main {
 4     public static Scanner scn = new Scanner(System.in);
 5     public static void main(String[] args) {
 6         int a,b;
 7         while(scn.hasNext()) {
 8             a = scn.nextInt();
 9             b = scn.nextInt();
10             System.out.println(a+b-tool.gcd(a, b));
11         }
12         System.exit(0);
13     }
14 }
15 class tool {
16     public static int gcd(int a, int b) {
17         int temp;
18         if (a < b) {
19             temp = a;
20             a = b;
21             b = temp;
22         }
23         while (b != 0){
24             temp = a;
25             a = b;
26             b = temp % b; 
27         }
28         return a;
29     }
30 }

2017-07-23 17:16:21