唯一分解定理
(质因数分解) 所有大于 (1) 的正整数都可以被唯一表示有限个质数的乘积形式（这个形式又可以叫标准分解式）
原理
通过筛法得到一个质数表，挨个挨个除，能整除多少次那这个质数就有多少次幂。枚举质数的范围应该是(2sim sqrt{n})（这个的原因请看推论-因数的合数大小）。这样把成对的因数除完还有可能剩下一个单独的质因数，再单独加到分解的结果中就可以了。
当然数据小的话不用质数表直接挨个枚举也应该不是问题
代码
（变量名与公式中的各项保持一致）
int pri[MX];//预处理完成后得到的质数表
int p[MX],a[MX];//p记录所有质因数的值,a记录所有质因数的幂,(记录方式和之前的pri记录方式一样)
void PrimeDevide(int num){
for(int i=1;i<pri[0] && pri[i]*pri[i]<=num;i++){
if(num%pri[i]==0){//找到因数
p[++p[0]]=pri[i];
while(num%pri[i]==0){//将该因数除去并根据循环次数统计幂
a[p[0]]++;
num/=pri[i];
}
}
}
if(num!=1){//可能剩下单个质因数
p[++p[0]]=num;
a[p[0]]=1;
}
}
推论
合数的因数大小
若 (n) 为合数，则其标准分解式中必满足 (exist p | n, pleq sqrt{n}) （这个其实相当于是约数的性质）
理解
因为因数必然是成对存在的嘛，一个小于(sqrt n)，一个大于(sqrt n)，（假设两个都小于，那么这两个的乘积一定小于 (n) ；假设两个都大于，那么这两个的乘积一定大于 (n) 。两个假设都矛盾，原结论得证）所以这个推论其实可以表示为通过确定 (1sim sqrt{n}) 范围的所有因数就可以找到 (n) 所有成对的因数
因数个数公式
通过对标准分解式中各个质因数的组合可以枚举出所有的因数，而这里组合的方案数就是因数的个数，它与标准分解式中质因数的指数是满足乘法原理的：（这里设因数个数为 (x) )
理解
对于 (n) 的每一个因数，都必然也可以用 (n) 的标准分解式的形式表示出来，不过有一点不同：(alpha_i)在这里是可以取到0的（也就是说这个因数不包含(p_i)这个质因子）。当我们要通过标准分解式构造因数时，每一个质因子的指数的不同的取法就是 (0simalpha_i) 一共 (alpha_i+1) 种，而且每一个质因子取多少次幂是独立的，那么总共取出来的方案数也就必然满足乘法原理，那么乘起来就好啦
因数和公式
同样是通过改变标准分解式中质因数的指数来计算的，只不过我们将单纯的质数相乘变成了这样：（这里设因数和为(sum)）
理解
如果只看一个质因数，那么在固定其他的情况下，这个因数就可以为因数和做出它所有次幂的贡献，然后还是乘起来就行啦