1.质因子分解
质因子分解是指将一个正整数n写成一个或多个质数的乘积形式，例如180=2x2x3x3x5。由于质因子都是质数，因此在计算质因子之前我们需要先得到质数表。
计算n的因子，首先先定义质因子的结构体，如下：
struct factor{
int x; //质因子
int cnt; //质因子的个数
}fac[10]; //对于int来说，不会超过10个质因子
接着是枚举1到sqrt(n)的所有质数p，判断p是否为n的因子：
1）如果是n的因子，则求出该p的次数
2）如果不是，则直接跳过
int sqr=(int)sqrt(1.0*n);
for(int i=0;i<count&&prime[i]<=sqr;i++){
if(n%prime[i]==0){
fac[num].x=prime[i];
fac[num].cnt=0;
whiie(n%prime[i]==0){
fac[num].cnt++;
n=n/prime[i];
}
num++;
}
}
如果最后n不为1，则表示该数有且只有一个大于sqrt(n)的因子：
if(n!=1){
fac[n].x=n;
fac[n].cnt=1;
num++:
}
2.大整数运算
大整数是指超过了编程语言定义的整数的范围的数进行运算，一般的算法只包括加法和减法运算。
1.大整数的存储
大整数的存储一般使用一个数组来存储大整数中每一位的数，遵循的原则是整数的高位存储在数组的高位，整数的低位存储在数组的低位。
char str[100010];
int a[100010];
gets(str);
int len=strlen(str);
for(int i=0;i<len;i++){
a[i]=str[len-1-i];
}
不过一般为了存储多个大整数的长度，是使用的结构体：
struct bign{
int d[1000];
int len;
bign(){ //构造函数赋初值
memset(d,0,sizeof(d))
len=0;
}
};
bign change(char str[]){
bign a;
int len=strlen(str);
a.len=len;
for(int i=0;i<len;i++){
a.d[i]=str[len-1-i];
}
return a;
}
2.大整数的比较
首先比较len，长的一方则大，如果len相同，则按照次序一位一位的比较即可。
bool compare(bign a,bign b){
if(a.len>b.len) return true;
else if(a.len<b.len) return false;
for(int i=0;i<a.len;i++){
if(a.d[i]>b.d[i]){
return true;
}
else if(a.d[i]<b.d[i]){
return false;
}
}
return 0; //相等
}
3.大整数加法
根据手算的步骤即可得出：
bign add(bign a,bign b){
bign c;
int carry=0;
for(int i=0;i<a.len||i<b.len;i++){
int temp=a.d[i]+b.d[i]+carry;
carry=temp/10;
c.d[i]=temp%10
c.len++;
}
if(carry!=0){
c.d[len++]=carry;
}
return c;
}
4.大整数减法
同样根据手算的步骤得出：
bign sub(bign a,bign b){
bign c;
int carry=0;
for(int i=0;i<a.len||i<b.len;i++){
if(a.d[i]<b.d[i]){
a.d[i+1]--;
a.d[i]=a.d[i]+10;
c.d[i]=a.d[i]-b.d[i];
c.len++;
}
else{
c.d[i]=a.d[i]-b.d[i];
c.len++;
}
}
while(c.len-1>=1 && c.d[c.len-1]==0){
c.len--; //去除高位的0同时保留至少一位
}
return c;
}
3.组合数
1.求解关于n!的问题
n!表示n的阶乘，在这里我们是要球求出n!中有多少个质因子p。例如6!=1x2x3x4x5x6，而其中有4个质因子2(2,2x2=4,2x3=6)，2个质因子3(3,2x3=6)。如果是直接按照直接求出1-n每个数中各有多少个质因子，则在题目中肯定会超时。所以在这里直接给出结论：
n!中有n/p + n/p^2 + n/p^3 + ...个质因子
//非递归写法
int cal(int n,int p){
int ans=0;
while(n){
ans=ans+n/p;
n=n/p;
}
return ans;
}
//递归写法
int cal(int n,int p){
if(n<p) return 0;
return n/p+cal(n,p^p); //return n/p+(n/p,p)
}
同时利用这个算法也可以求出n!的末尾有多少个0，即只用求出n!有多少个5即可(p=5)。
2.组合数的计算
组合数是指从n个不同元素中选出m个元素的方案数(m<=n)，一般可以写成C(n,m)。在求解组合数时可以根据组合数的性质：C(n,m)=C(n-1,m-1)+C(n-1,m)来进行计算：
long long C(long long n,long long m){
if(m==1 || m==n) return 1;
return C(n-1,m)+C(n-1,m-1);
}
在上述算法中递归的过程中，会有大量的重复计算，所以可以对算法进行改进：
long long res[101][101]={0};
long long C(long long n,long long m){
if(m==0 || m==n) return 1;
if(res[n][m]!=0) return res[n][m]; //记录已经计算过的组合数
return res[n][m]=C(n-1,m)+C(n-1,m-1);
}
此时算法时间复杂度为O(n^2)。
网友评论