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代码：

#include 
 
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;
}