一、最大公约数gcd

约数和倍数的定义（百度百科）

整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。
显然，任何非0整数是0的约数，0不是任何数的约数。

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

二、最小公倍数lcm

定理：lcm(a,b)gcd(a,b)=ab

证明：设x和y的最大公约数为a，则最小公倍数为(x/a)(y/a)a=xy/a，最大公约数和最小公倍数的乘积为xy/aa=xy，证毕。

int lcm(int a,int b){return a/gcd(a,b)*b;//注意技巧：先除再乘，可避免乘法溢出
}

三、唯一分解定理

任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积N=p1^a1*p2a2*…*pn^an这里p1<p2<…<pn均为质数，各指数ai是正整数。
这样的分解称为N的标准分解式。

定理应用：
一个大于1的自然是N，根据其标准分解式，可以求出其正因子个数是(a1+1)(a2+1)…(an+1)，全体正因子之和是（1+p1+p1^2+…+p1a1）（1+p2+p2^2+…+p2a2）…（1+pn+pn^2+…+pnan）。

下面是唯一分解定理的粗糙代码实现：

#include<iostream>
#include<cmath>
using namespace std;typedef struct{int x,y;
}node;node a[1000];
int j=0;int solve(int n){j=0;for(int i=2;i<=n;i++){if(n%i==0){int cnt=1;n/=i;while(n%i==0){cnt++;n/=i;}a[j].x=i;a[j++].y=cnt;}}
}int main()
{int T,n;cin>>T;while(T--){cin>>n;solve(n);for(int i=0;i<j;i++){cout<<a[i].x<<" "<<a[i].y<<endl;}}return 0;
}

【例题Choose and divide UVA - 10375 】

题意：已知C(m,n)=m! / (n!*(m-n!)),输入整数p,q,r,s(p>=q,r>=s,p,q,r,s<=10000)，计算C(p,q)/C(r,s)。输出保证不超过10^8，保留5位小数

【代码】
参考刘汝佳《算法竞赛入门经典》（第2版）

#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
#include<cstdio>
using namespace std;const int maxn=10000+5;vector<int>prime;
bool vis[maxn];
int e[maxn];//把10000以内的所有素数给晒出来
void init(){memset(vis,0,sizeof(vis));for(int i=2;i<maxn;i++)for(int j=2*i;j<maxn;j+=i)vis[j]=1;for(int i=2;i<maxn;i++)if(!vis[i]) prime.push_back(i);
}
//一个一个整数用素数给消耗掉，转化成素数指数幂形式（唯一分解定理）
void add_integer(int n,int d){for(int i=0;i<prime.size();i++){while(n%prime[i]==0){n/=prime[i];e[i]+=d;}if(n==1) break;}
}
//把整个阶乘按照一个数一个数的拆成指数幂
void add_factorial(int n,int d){for(int i=1;i<=n;i++)add_integer(i,d);
}int main()
{init();int p,q,r,s;while(cin>>p>>q>>r>>s){memset(e,0,sizeof(e));add_factorial(p,1);add_factorial(q,-1);add_factorial(p-q,-1);add_factorial(s,1);add_factorial(r-s,1);add_factorial(r,-1);double ans=1;for(int i=0;i<prime.size();i++)ans*=pow(prime[i],e[i]);printf("%.5lf\n",ans);}return 0;
}