【数论】最大公约数、约数的个数与约数之和定理
Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。
🌈个人主页：主页链接
🌈算法专栏：专栏链接
我会一直往里填充内容哒！
🌈LeetCode专栏：专栏链接
目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出
🌈代码仓库：Gitee链接
🌈点击关注=收获更多优质内容🌈
用辗转相除法求最大公约数，以及数论相关的知识：约数个数与约数和的定理，及代码实现
目录
题目:最大公约数
题解:
代码实现:
题目:约数个数
题解:
代码实现:
题目:约数之和
题解:
代码实现:
完结撒花：
先来科普下什么是约数：当a能被b整除，我们就说b为a的约数，b的倍数为a
题目:最大公约数
题解:
这里我们用到了辗转相除法 先读入a与b这两个数，之后把a与b相除，令其结果为c，若c不为0，则令a=b，b=c（辗转就是体现在了这里），若c为0，则说明b为a的最大公约数，则输出b即可
代码实现:
#include
using namespace std;
int gcd(int a,int b)
{return b?gcd(b,a%b):a;
}
int main()
{int n=0;cin>>n;while(n--){int a,b;cin>>a>>b;cout< 题目:约数个数
题解:
这里先科普一个数学知识，约数个数定理，假设这个数为16，求出他的质因子为2，其指数为4
那么其约数的个数就为指数加一（4+1）
可以这样理解
第一个约数为其因子的1次方2，第二个约数为其因子的二次方2*2
第三个约数为其因子的三次方2*2*2
第四个约数为其因子的四次方2*2*2*2 第五个约数为其因子的0次方也就是1
再举一个例子：
所以360的约数个数就为（3+1）*（2+1）*（1+1）
这就是约数个数定理
回顾一下 我们要做的就是将一个数求出他每一个质因子（不会的uu们可以看看这篇文章分解质因数）并记录其指数情况。之后将指数拿出来做乘法就ok了
这里用hash表记录其质因子与指数的情况，其中key为质因子 value为指数，所以最后的表达式就为指数value，所以最后就将其加一再相乘即可。
代码实现:
#include
#include
using namespace std;
const int N=1e9+7;
int main()
{unordered_mapmap;int n=0,s;cin>>s;while(s--){cin>>n;for(int i=2;i<=n/i;i++){while(n%i==0){n/=i;map[i]++;}}if(n>1)map[n]++;}long long res=1;for(auto ma:map){long long p=1;int a=ma.second;res=(res*(a+1))%N;}cout< 题目:约数之和
题解:
上面学了约数个数的定理，现在我们再来学一下约数之和定理，同样非常的简单
仍然以16来举例子，其质因子为2指数为4.
所以其约数之和为（2^0+2^1+2^2+2^3+2^4）=31
再来举上面360的例子：
所以其约数之和为1261
这就是约数之和定理。
回顾一下 我们要做的就是将一个数求出他每一个质因子（不会的uu们可以看看这篇文章分解质因数）并记录其指数情况。之后将其拿出来先相加再做乘法就ok了
这里用hash表记录其质因子与指数的情况，其中key为质因子 value为指数，所以最后的表达式就为指数value与其质因子，先相加再相乘就好。
代码实现:
#include
#include
using namespace std;
const int N=1e9+7;
int main()
{unordered_mapmap;int n=0,s;cin>>s;while(s--){cin>>n;for(int i=2;i<=n/i;i++){while(n%i==0){n/=i;map[i]++;}}if(n>1)map[n]++;}long long res=1;for(auto ma:map){long long p=1;int a=ma.second;while(a--)p=(p*ma.first+1)%N;res=res*p%N;}cout< 完结撒花：
🌈本篇博客的内容【数论：最大公约数、约数的个数与约数之和定理】已经结束。
🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。
🌈诸君，山顶见！