XTU-OJ 1172-因子和-Toy模板网

这篇具有很好参考价值的文章主要介绍了XTU-OJ 1172-因子和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

给一个正整数n，请求n所有因子的累加和。

输入

每行一个整数n，1≤n≤100,000,000。如果n为0表示输入结束，不需要处理。

输出

每行输出一个结果。

样例输入
1
2
3
4
0
样例输出
1
3
4
7

解题思路：一眼看见数据 n 最大能到 1e8，用暴力不知道是否会超时，这里就继续沿用质因数分解的思路来求解。

任何数都可以分解成质因数的乘积: n = a^x * b^y * c^z * ·····

如：14 = 2*7 、 36 = 2^2*3^2

因子和就等于 (a^0 + a^1 +····+ a^x) * (b^0 + b^1 +····+ b^y) * (c^0 + c^1 +····+ c^z) * ·····。

AC代码：文章来源地址https://www.toymoban.com/news/detail-720747.html

#include <stdio.h>
 
int main()
{
    int num[20][3] = {0};
    int n,cnt,i,j;
    __int64 sum,Co_sum,Co_num;
    while (scanf("%d",&n) != EOF && n != 0) 
    {
        cnt = 0; sum = 1; 
        for (i=2; i*i<=n; i++) 
        {
            if (n%i == 0)  // 找到所有的质因数,保存质因数及其指数
            {
                for (j=0; n%i==0; j++) n/=i;      
                num[cnt][0] = i, num[cnt][1] = j; // num[][0] 记录 质因数, num[][1] 记录 该质因数指数
                cnt ++;
            }
        }
        if (n != 1)    {num[cnt][0] = n, num[cnt][1] = 1; cnt ++;}
 
        for (int i = 0; i < cnt; i ++)            // 计算因子和
        {
            Co_num = 1, Co_sum = 0;
            for (int j = 0; j <= num[i][1]; j ++) // 先算出 质因子(Xi^0 + Xi^1 + Xi^2 +···+ Xi^n-1 + Xi^n) 之和
            {
                Co_sum += Co_num;
                Co_num *= num[i][0];
            }
            sum *= Co_sum;                       // 各项指数和之间 相乘
        }// 关键理解： n的因子和 = (a^0 + a^1 +···+ a^x) * (b^0 + b^1 +···+ b^y) * (c^0 + c^1 +···+ c^z) * ···
        printf("%I64d\n",sum);
    }
    return 0;
}

到了这里，关于XTU-OJ 1172-因子和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！