SRM遇到的一个数论技巧——最大公约数和最小公倍数的关系

最⼤公约数L和最⼩公倍数G的关系：1、L%G == 0；

2、设A, B的最⼤公约数为G， 最⼩公倍数为L，则：L/G = （A/G）*（B/G）3、gcd(A/G, B/G) = 1;

题⽬：给出⼀对数A， B 的最⼤公约数G， 最⼩公倍数L。这⾥A， B有多种组合。，求A，B的⼀种组合使得A + B最⼩。如果没有则输出-1（SRM535 div2 500pt）(G <= 10^12, L<=10^12)

猛的⼀看数据很⼤。不过⽤上前边的定理就可以解决了。领X = L/G；

枚举A/G的值（不超过sqrt(X)），得到B/G的值。判断是否满⾜定理3。在所有满⾜的情况中找最⼩的ans = min(ans, （A/G + B/G）)。最后结果为ans*G 代码：

1 #include 2 #include 3 #include

21 using namespace std;22 23

24 class FoxAndGCDLCM {25 public:

26 long long gcd(long long a, long long b) {27 if(b == 0) return a;28 return gcd(b, a%b);29 }30

31 long long get(long long G, long long L) {32

33 if(L%G) return -1;34 long long i, x = L/G;35 long long ans = L;36

37 for(i = 1; i*i <= x; ++i) {38 if(x%i) continue;39 if(gcd(i, x/i) == 1) {

40 ans = min(ans, i + x/i);41 }42 }

43 return ans*G;44 }45 };46 47

48

49 //Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!