最大公约数（greatest common divisor）
欧几里得辗转相除法：
gcd(x,y)表示x和y的最大公约数
进入运算时:x!=0,y!=0，本质上就是不断转换成求等价更小数的最大公约数。如果x%y=0，返回y，即最大公约数。
gcd(x,y)=gcd(y,x%y)
证明：
设k=x/y，b=x%y 则：x=ky+b
如果n能够同时整除x和y，则(y%n)=0,(ky+b)%n=0，则b%n=0，即n也同时能够整除y和b。
由上得出：同时能够整除y和(b=x%y)的数，也必然能够同时整除x和y。故而gcd(x,y)=gcd(y,x%y)。当(b=x%y)=0，即y可以整除x，这时的y也就是所求的最大公约数了。
附上两条重要性质：gcd(a,b)=gcd(b,a)，gcd(-a,b)=gcd(a,b)
最小公倍数（least common multiple）
公式解法：
最小公倍数=两数之积/最大公约数
package mainimport ("fmt")/**穷举法：最大公约数 */func gcdNormal(x, y int) int {var n intif x > y {n = y} else {n = x}for i := n; i >= 1; i-- {if x%i == 0 && y%i == 0 {return i}}return 1}/**辗转相除法：最大公约数*递归写法，进入运算是x和y都不为0 */func gcd(x, y int) int {tmp := x % yif tmp > 0 {return gcd(y, tmp)} else {return y}}/**辗转相除法：最大公约数*非递归写法 */func gcdx(x, y int) int {var tmp intfor {tmp = (x % y)if tmp > 0 {x = yy = tmp} else {return y}}}/**穷举写法：最小公倍数 */func lcmNormal(x, y int) int {var top int = x * yvar i = xif x < y {i = y}for ; i <= top; i++ {if i%x == 0 && i%y == 0 {return i}}return top}/**公式解法：最小公倍数=两数之积/最大公约数 */func lcm(x, y int) int {return x * y / gcd(x, y)}func main() {x, y := 12, 15fmt.Println("gcdNormal=", gcdNormal(x, y))fmt.Println("gcd=", gcd(x, y))fmt.Println("gcdx=", gcdx(x, y))fmt.Println("lcmNormal=", lcmNormal(x, y))fmt.Println("lcm=", lcm(x, y))}
猜生日问题：
小明对生日十分看重，因为他可以得到祝福，可以和朋友亲人一起分享快乐，可以为自己的人生做一次总结，并且...能够收到好多礼物！不过小明是个神秘的人，不会轻易告诉你他的生日，现在他想到一个办法，让你去猜他的生日是哪一天。
小明会告诉你如下三个信息：
1. 出生月份和出生日子的最大公约数；
2. 出生月份和出生日子的最小公倍数；
3. 出生年份；
现在要求你猜出小明的生日。 Input 第一行输入一个正整数T，表示总共有T组册数数据(T <= 200)；
对于每组数据依次输入三个数x，y，z，
x表示出生月份和出生日子的最大公约数(1<= x <=1000)；
y表示出生月份和出生日子的最小公倍数(1<= y <=1000)；
z表示出生年份（1900 <= z <= 2013）。
每组输入数据占一行。 Output 对于每组数据，先输出Case数。
如果答案不存在 ，输出“-1”；
如果答案存在但不唯一 ，输出“1”；
如果答案唯一，输出生日，日期格式为YYYY/MM/DD； 直接给出Go语言实现代码（为便于测试输入问题已忽略）
package mainimport ("fmt")/*检查如期是否合法*/func checkDate(y, m, d int) int {var arr [13]int = [13]int{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}//闰年if (y%4 == 0 && y%100 != 0) || y%400 == 0 {arr[2] = 29}if arr[m] < d {return 0}return 1}/**已知x和y的最小公倍数min和最大公约数max，求x和y*由最小公倍数性质：min=x*y/max，所以x*y=max*min*由最大公约数性质：x和y都可以写成max*n */func rgcd(min, max, y int, m, d *int) int {var mMax, dMax, res, count, tmp int = 12 / max, 31 / max, min * max, 0, 0for i := 1; i <= mMax; i++ {for j := 1; j <= dMax; j++ {tmp = max * i * max * jif tmp > res {break} else if tmp == res {//计算得到的日期的合法，才加上tmpM := max * itmpD := max * jif checkDate(y, tmpM, tmpD) == 1 {*m = tmpM*d = tmpD//fmt.Println(*m, *d)count++}}}}if count > 1 {return 1} else if count == 1 {return 0} else {return -1}}func main() {min, max, y, m, d := 24, 3, 1999, 0, 0fr := rgcd(min, max, y, &m, &d)if fr == 0 {fmt.Printf("%d/%02d/%02d", y, m, d)} else {fmt.Println(fr)}}
