烟台网站建设推荐企汇互联见效付款,公司logo设计理念说明,前端网站建设,清丰网站建设费用Halo#xff0c;这里是Ppeua。平时主要更新C语言#xff0c;C#xff0c;数据结构算法......感兴趣就关注我吧#xff01;你定不会失望。 #x1f308;个人主页#xff1a;主页链接 #x1f308;算法专栏#xff1a;专栏链接 我会一直往里填充内容哒#xff01; … Halo这里是Ppeua。平时主要更新C语言C数据结构算法......感兴趣就关注我吧你定不会失望。 个人主页主页链接 算法专栏专栏链接 我会一直往里填充内容哒 LeetCode专栏专栏链接 目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目也会当天做完发出 代码仓库Gitee链接 点击关注收获更多优质内容 用辗转相除法求最大公约数以及数论相关的知识约数个数与约数和的定理及代码实现 目录
题目:最大公约数
题解:
代码实现:
题目:约数个数 题解:
代码实现: 题目:约数之和 题解:
代码实现:
完结撒花 先来科普下什么是约数当a能被b整除我们就说b为a的约数b的倍数为a
题目:最大公约数 题解:
这里我们用到了辗转相除法 先读入a与b这两个数之后把a与b相除令其结果为c若c不为0则令abbc辗转就是体现在了这里若c为0则说明b为a的最大公约数则输出b即可 代码实现:
#includeiostream
using namespace std;
int gcd(int a,int b)
{return b?gcd(b,a%b):a;
}
int main()
{int n0;cinn;while(n--){int a,b;cinab;coutgcd(a,b)endl;}return 0;
}
题目:约数个数 题解:
这里先科普一个数学知识约数个数定理假设这个数为16求出他的质因子为2其指数为4
那么其约数的个数就为指数加一41
可以这样理解
第一个约数为其因子的1次方2第二个约数为其因子的二次方2*2
第三个约数为其因子的三次方2*2*2
第四个约数为其因子的四次方2*2*2*2 第五个约数为其因子的0次方也就是1 再举一个例子
所以360的约数个数就为31*21*11
这就是约数个数定理
回顾一下 我们要做的就是将一个数求出他每一个质因子不会的uu们可以看看这篇文章分解质因数并记录其指数情况。之后将指数拿出来做乘法就ok了 这里用hash表记录其质因子与指数的情况其中key为质因子 value为指数所以最后的表达式就为指数value所以最后就将其加一再相乘即可。
代码实现:
#includeiostream
#includeunordered_map
using namespace std;
const int N1e97;
int main()
{unordered_mapint,intmap;int n0,s;cins;while(s--){cinn;for(int i2;in/i;i){while(n%i0){n/i;map[i];}}if(n1)map[n];}long long res1;for(auto ma:map){long long p1;int ama.second;res(res*(a1))%N;}coutres;
} 题目:约数之和 题解:
上面学了约数个数的定理现在我们再来学一下约数之和定理同样非常的简单
仍然以16来举例子其质因子为2指数为4.
所以其约数之和为2^02^12^22^32^431
再来举上面360的例子 所以其约数之和为1261
这就是约数之和定理。 回顾一下 我们要做的就是将一个数求出他每一个质因子不会的uu们可以看看这篇文章分解质因数并记录其指数情况。之后将其拿出来先相加再做乘法就ok了 这里用hash表记录其质因子与指数的情况其中key为质因子 value为指数所以最后的表达式就为指数value与其质因子先相加再相乘就好。
代码实现:
#includeiostream
#includeunordered_map
using namespace std;
const int N1e97;
int main()
{unordered_mapint,intmap;int n0,s;cins;while(s--){cinn;for(int i2;in/i;i){while(n%i0){n/i;map[i];}}if(n1)map[n];}long long res1;for(auto ma:map){long long p1;int ama.second;while(a--)p(p*ma.first1)%N;resres*p%N;}coutres;
}
完结撒花 本篇博客的内容【数论最大公约数、约数的个数与约数之和定理】已经结束。 若对你有些许帮助可以点赞、关注、评论支持下博主你的支持将是我前进路上最大的动力。 若以上内容有任何问题欢迎在评论区指出。若对以上内容有任何不解都可私信评论询问。 诸君山顶见
