最大公约数原理(转)

源地址:http://blog.sina.com.cn/s/blog_67e046d10100reqb.html
1、最大公约数原理
设d = gcd(A1, A2, …, An),则必然可以找到或正或负的整数Xi, 使
A1X1 + A2X2 + … + AnXn = d
证明:回想一下多个数求gcd的方法,可知gcd(A1, A2, …, An) = gcd(A1, gcd(A2, A3, …, An))。对序列(A1, A2, …, An)进行如下操作:从i = 1开始,设j = i + 1,若gcd(Ai, Aj) = k > 1,则将Aj修改为k,注意k是可以由Ai*p + Aj*q得到的。操作一直进行到最后,若全部修改完后,左边必为gcd(A1, A2, …, An),而右边必可写成A1X1 + A2X2 + … + AnXn,得证!
2、A1X1 + A2X2 + … + AnXn = 1有解的充要条件是d = gcd(A1, A2, …, An) = 1
证明:
①、方程左边必整除d,故方程右边必整除d,因而方程有解 => d = 1。
②、若d = 1,则由最大公约数原理可知,必存在一系列或正或负整数Xi,使A1X1 + A2X2 + … + AnXn = d = 1。
统合①、②,命题得证!

hdoj1568

这题碉堡了,第一感觉是大数,但是感觉写起来很烦,而且只要求前几位,这就意味着求出整个fib(n)是不必要的,于是这个想法枪毙掉。接下来想到的是数论,由于本菜鸟数论方面涉猎甚浅,只会解解不定方程的水平,于是各种yy之后,无果。。其实一直在想会不会和科学记数法有关,因为以前遇到过求n!的第一位的题目,但是始终想不到如何联系到科学记数法。。
无奈只能上网查,原来要用到fib的通项公式。。看来自己还是不够敏感阿~
这题以后再写思路,不然满脑子网上的解题思路,就没意思了
记下知识点:1.科学记数法。2.fib通项公式
注意精度问题~

gcd和lcm 居然忘掉了这个。。

/*==================================================*\ 
| GCD 最大公约数 
\*==================================================*/ 
int gcd(int x, int y)
{ 
    if (!x || !y) return x > y ? x : y; 
    for (int t; t = x % y; x = y, y = t); 
    return y; 
} 
/*==================================================*\ 
| 快速 GCD 
\*==================================================*/ 
int kgcd(int a, int b)
{ 
    if (a == 0) return b; 
    if (b == 0) return a; 
    if (!(a & 1) && !(b & 1)) 
        return kgcd(a>>1, b>>1)<<1;
    else if (!(b & 1))
    return kgcd(a, b>>1); 
    else if (!(a & 1)) return kgcd(a>>1, b); 
    else return kgcd(abs(a - b), min(a, b)); 
} 
/*==================================================*\ 
| 扩展 GCD  
| 求x, y使得gcd(a, b) = a * x + b * y;  
\*==================================================*/ 
int extgcd(int a, int b, int & x, int & y)
{ 
    if (b == 0) { x=1; y=0; return a; } 
    int d = extgcd(b, a % b, x, y); 
    int t = x; x = y; y = t - a / b * y; 
    return d; 
} 

以上代码转自兔子的算法集中营。
lcm只需lcm=a/gcd(a,b)*b即可
至于求一组数的gcd和lcm
可以先求两个数的,在用求出的gcd与第三个数求gcd,以此类推,代码样例: