先前我们已经介绍过了怎么判断质数和约数,现在我们对于约数的个数和约数之和也要进行求解,而求解的方法就是根据算术基本定理来的!
先介绍一下什么是算术基本定理:
算术基本定理可表述为:任何一个大于1的自然数 N,如果N不为质数,那么N可以唯一分解成有限个质数的乘积 N=P1^a1P2^a2P3^a3……Pn^an,这里P1
那么一直这个之后我们是不是可以知道这个自然数N的约数也是这样的形式D=P1^b 1P2^b 2P3^b 3……Pn^b n,(0
以下是代码:
include
define mod 1000000007
using namespace std;
typedef long long LL;
unordered_map
int main()
{
int n;
cin >> n;
LL ans = 1;
while (n — )
{
int x;
cin >> x;
for(int i = 2;i
那么这样的话我们再来看看约数之和怎么算,我们刚刚已经知道了约数的形式是这样的D=P1^b 1P2^b 2P3^b 3……Pn^b n,所以所有的约数是不是相当于每个P1,P2,……Pn都出一个指数幂,然后求和;我们可以发现约数之和即为:(P1^0+P1^1+P1^2……+P1^a1)……(Pn^0+Pn^1+Pn^2……+Pn^a1);
接下来看代码:
include
define mod 1000000007
using namespace std;
typedef long long LL;
unordered_map
int main()
{
LL ans = 1;
int n;
cin >> n;
while (n — )
{
int x;
cin >> x;
for(int i = 2;i
Original: https://www.cnblogs.com/ZheyuHarry/p/16099930.html
Author: ZheyuHarry
Title: 利用算术基本定理求解约数个数 + 约数之和
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/583608/
转载文章受原作者版权保护。转载请注明原作者出处!