一.分解质因数和算术基本定理\n ① 惟一分解定理 (算术基本定理)可表述为：任何一个大于1的自然数N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=，这里P1\u003CP2\u003CP3......\u003CPn均为质数，其中指数ai是正整数。这样的分解称为N的标准分解式。\n\n ②质因数（素因数或质因子）在数论里是指能整除给定正整数的质数。除了1以外，两个没有其他共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以用指数表示。根据算术基本定理，任何正整数皆有独一无二的质因子分解式。只有一个质因子的正整数为质数。\n\n如何分解质因数\n分解质因数，也就是将n表示为标准分解式。所以我们要求出质因数和对应的指数。\n\n试除法：\n\n为什么只要枚举到sqrt(n)就行呢？\n\n因为超过sqrt(n)的部分基本没有意义，因为如果存在多个大于sqrt(n)的质因数，根据惟一分解定理，n由这些数相乘组成，那么多个大于sqrt(n)的质因数相乘就超过了n，矛盾。\n\n所以最多只会有一个大于sqrt(n)的质因数，所以当枚举到sqrt(n)时剩下的数不等于1，那么说明还剩下这个大于sqrt(n)的质因数。额外加上即可。
vector<pair<int,int>> div(int n){
vector<pair<int,int>> ans;
//因为惟一分解定理，合数也是由多个质数组成，合因数组成的较小质数会被先分解，所以每次得到的必定是质因数
for(int j=2;j<=n/j;j++){//除净小于sqrt(n)的质因数
int sum=0;
while(n%j==0){//除净质因数
n/=j;
sum++;//该质因数的指数
}
if(sum!=0)
ans.push_back({j,sum});
}
if(n>1)//大于sqrt(n)的质因数只会有一个，如果有多个，分解定理的乘积就大于n了
ans.push_back({n,1});
return ans;
}
unordered_map<int,int> div(int n){//得到质因数
unordered_map<int,int>ans;
for(int j=2;j<=n/j;j++){
if(n%j==0){
while(n%j==0){
n/=j;
ans[j]++;
}
}
}
if(n>1)ans[n]++;
return ans;
}
