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<iostream> 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<<gcd(a,b)<<endl; } return 0; }
题目:约数个数
题解:
这里先科普一个数学知识，约数个数定理，假设这个数为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<iostream> #include<unordered_map> using namespace std; const int N=1e9+7; int main() { unordered_map<int,int>map; 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<<res; }
题目:约数之和
题解:
上面学了约数个数的定理，现在我们再来学一下约数之和定理，同样非常的简单
仍然以16来举例子，其质因子为2指数为4.
所以其约数之和为（2^0+2^1+2^2+2^3+2^4）=31
再来举上面360的例子：
所以其约数之和为1261
这就是约数之和定理。
回顾一下 我们要做的就是将一个数求出他每一个质因子（不会的uu们可以看看这篇文章分解质因数）并记录其指数情况。之后将其拿出来先相加再做乘法就ok了
这里用hash表记录其质因子与指数的情况，其中key为质因子 value为指数，所以最后的表达式就为指数value与其质因子，先相加再相乘就好。
代码实现:
#include<iostream> #include<unordered_map> using namespace std; const int N=1e9+7; int main() { unordered_map<int,int>map; 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<<res; }
完结撒花：
🌈本篇博客的内容【数论：最大公约数、约数的个数与约数之和定理】已经结束。
🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。
🌈诸君，山顶见！
