辗转相除法

求最大公约数
最小公倍数 = ab/最大公约数

1
2
3

long gcd(long a, long b) {
    return a == 0 ? b : gcd(b % a, a);
}

1
2
3
4
5
6
7
8

long gcd(long a, long b) {
    long tmp;
    while ((tmp = a % b) != 0) {
        a = b;
        b = tmp;
    }
    return b;
}

前言

通过数论或者自然数性质完美解决的三个常见博弈游戏：

简介

原作者博客

0、排序算法说明
0.1 排序的定义

对一序列对象根据某个关键字进行排序。

Bash游戏

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1066

有一堆石子共有N个。A B两个人轮流拿，A先拿。每次最少拿1颗，最多拿K颗，拿到最后1颗石子的人获胜。
假设A B都非常聪明，拿石子的过程中不会出现失误。给出N和K，问最后谁能赢得比赛。

例如N = 3，K = 2。无论A如何拿，B都可以拿到最后1颗石子。

https://www.nowcoder.com/test/question/28c1dc06bc9b4afd957b01acdf046e69?pid=1725829&tid=14425231

给定一个字符串s，你可以从中删除一些字符，使得剩下的串是一个回文串。如何删除才能使得回文串最长呢？
输出需要删除的字符个数。

输入描述:
输入数据有多组，每组包含一个字符串s，且保证:1<=s.length<=1000.

输出描述:
对于每组数据，输出一个整数，代表最少需要删除的字符个数。

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1136

对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。
此函数以其首名研究者欧拉命名，它又称为Euler’s totient function、φ函数、欧拉商数等。
例如：φ(8) = 4（Phi(8) = 4），因为1,3,5,7均和8互质。

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1002

一个高度为N的由正整数组成的三角形，从上走到下，求经过的数字和的最大值。
每次只能走到下一层相邻的数上，例如从第3层的6向下走，只能走到第4层的2或9上。

1
2
3
4

   5
  8 4
 3 6 9
7 2 9 5

例子中的最优方案是：5 + 8 + 6 + 9 = 28

最长回文子串

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1088

回文串是指aba、abba、cccbccc、aaaa这种左右对称的字符串。
输入一个字符串Str，输出Str里最长回文子串的长度。