1.欧几里得算法（辗转相除法）
该算法用来快速计算两个整数的最大公约数。
递归算法：
int gcd(int a,int b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
非递归算法：
//辗转相除法
int gcd(int a,int b)
{
int x, y;
x = a>b?a:b;
y = a<b?a:b;
while(y != 0)
{
int temp = x;
x = y;
y = temp%y;
}
return x;
}
题目：
蒜头君和花椰妹在玩一个游戏，他们在地上将 n颗石子排成一排，编号为 1 到 n。开始时，蒜头君随机取出了 2 颗石子扔掉，假设蒜头君取出的2颗石子的编号为a,b。游戏规则如下，蒜头君和花椰妹2人轮流取石子，每次取石子，假设某人取出的石子编号为i，那么必须要找到一对 j,k 满足 i=j−k 或者 i=j+k ，并且编号为j，k 的石子已经被取出了，如果谁先不能取石子了，则视为输了。蒜头君比较绅士，让花椰妹先手。
输入格式
第一行输入一个整数t(1≤t≤500)，表示蒜头君和花椰妹进行了 t 局游戏。
对于每局游戏，输入 33 个整数 n,a,b。n(2≤n≤20000),a,b(1≤a,b≤n)，保证a,b 不相等。
输出格式
如果蒜头君赢了游戏，输出一行suantou，如果花椰妹赢了，输入一行huaye。
样例输入
5
8 6 8
9 6 8
10 6 8
11 6 8
12 6 8
样例输出
suantou
suantou
huaye
huaye
suantou
题目分析：
1. 首先蒜头取出两个石子编号为a和b。并且要求之后取出的石子必须满足有两个空位j和k的差或者和等于取出的石子i。
2. 首先第一个数肯定是根据a和b来取的。那就看比如15和9，那么取出6, 6 = 15-9；下一次取出3， 3 = 9-6，之后比三小的肯定能再取了，都不满足。然后就是去12， 12 = 9 + 3。……
3. 发现一件事，其实就是3就是15和9的最大公约数。凡是3包括3的倍数的都可以被取走。因为a+b的值必然是最大公约数的倍数。
4. 那题目就是求出第一次取出的a、b的最大公约数，然后算法满足最大公约数倍数的数字有多少个。蒜头妹是先手，就能推断出那个会赢。偶数个蒜头君赢，奇数个妹赢。
代码如下：
#include <iostream>
using namespace std;
int gcd(int a,int b)
{
if(b==0)
return a;
return gcd(b,a%b);
}
int main() {
int t;
cin>>t;
int a[501][3];
for(int i=0;i<t;i++)
{
cin>>a[i][0]>>a[i][1]>>a[i][2];
}
for(int i=0;i<t;i++)
{
int tmp=gcd(a[i][1],a[i][2]);
int count=a[i][0]/tmp;
if((count)%2==0)cout<<"suantou\n";
else cout<<"huaye\n";
}
return 0;
}
2. 素数筛选
判断一个数是不是素数，最简单暴力的方法是从概念出发，从2到n-1，每个数都来被n取余操作，只要有一个余数为零。说明就能整除。稍微优化一下是。假设i*j = n。那么既然n可以整除i必然可以整除j。所以，只需要判断2到sqrt(n)之间的数就可以。
一种比较好的方法是，一个合数肯定会有质因子，那么给质因子不断乘以倍数吗，得到的数字就都是合数。初始令2到N上面的数字位置1，表示都是素数。然后可知2i、3i、……都是合数，置0。这么算法的时间复杂度是N/2+N/3+N/4+……N/N，时间复杂度是O(nlog(n))。代码如下
for(int i=2;i<=n;i++)
isPrime[i]=1;
for(int i=2;i*i<=n;i++)
{
if(isPrime[i])
for(int j=i*i;j<=n;j+=i)
isPrime[j]=0;
}
题目：
有一天蒜头君突发奇想，他有一个猜想，任意一个大于2的偶数好像总能写成 2个质数的和。蒜头君查了资料，发现这个猜想很早就被一个叫哥德巴赫的人提出来了，称为哥德巴赫猜想。目前还没有证明这个猜想的正确性。蒜头君告诉你一个整数n，让你用这个数去验证。注意 1不是质数。
输入格式
输入一个偶数 n(2<n≤8000000)
输出格式
输出一个整数表示有多少对(x,y)满足 x + y = n(x≤y) 且x,y均为质数。
样例输入1
6
样例输出1
1
题目分析：
此题比较简单。具体来讲，求出小于n的所有质数，然后判断小于等于n/2的所有质数i和n-i是不是都是质数就好了。关键在于求出小于n的所有质数。
代码如下：
#include <iostream>
using namespace std;
bool isPrime[8000002];
int main() {
int n;
cin>>n;
// 初始化素数数组
for(int i=2; i<=n; ++i)
isPrime[i] = true;
// 求解所有素数
for(int i=2; i*i<=n; ++i)
{
for(int j=i*i; j<=n; j +=i)
{
isPrime[j] = false;
}
}
int count = 0;
for(int i=2; i<=n/2; ++i)
{
if(isPrime[i] && isPrime[n-i])
++count;
}
cout << count <<endl;
return 0;
}
3. 二分快速幂（pow（）函数）
求一个整数a的b次幂。除了利用函数pow外。自己写的时候，如果b是偶数。则a^b = (a^b/2)^2，b是奇数，a^b = (a^（b/2-1）)^2*a。
递归写法：
// 求幂产生很大的数通常伴随取模
int Pow_mod(int a, int b, int mod)
{
if(b == 0)
return 1%mod;
int temp = Pow_mod(a, b/2, mod);
temp = temp*temp%mod;
if(b%2 == 1)
temp = temp*a%mod;
return temp;
}
非递归写法：
// 非递归
int Pow_mod(int a, int b, int mod)
{
int res=1,temp=a;
for(; b; b/2)
{
if(b&1)
{
res = res*temp%mod;
}
temp = temp*temp%mod;
}
return res;
}
![数论-扩展欧几里得算法[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)