題目描述
給一個(gè)正整數(shù)n，請(qǐng)求n所有因子的累加和。
輸入
每行一個(gè)整數(shù)n，1≤n≤100,000,000。如果n為0表示輸入結(jié)束，不需要處理。
輸出
每行輸出一個(gè)結(jié)果。
樣例輸入
1 2 3 4 0樣例輸出
1 3 4 7
解題思路：一眼看見(jiàn)數(shù)據(jù) n 最大能到 1e8，用暴力不知道是否會(huì)超時(shí)，這里就繼續(xù)沿用 質(zhì)因數(shù)分解 的思路來(lái)求解。
任何數(shù)都可以分解成質(zhì)因數(shù)的乘積:? ?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) * ·····。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-720747.html
AC代碼：文章來(lái)源地址http://www.zghlxwxcb.cn/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) // 找到所有的質(zhì)因數(shù),保存質(zhì)因數(shù)及其指數(shù)
{
for (j=0; n%i==0; j++) n/=i;
num[cnt][0] = i, num[cnt][1] = j; // num[][0] 記錄 質(zhì)因數(shù), num[][1] 記錄 該質(zhì)因數(shù)指數(shù)
cnt ++;
}
}
if (n != 1) {num[cnt][0] = n, num[cnt][1] = 1; cnt ++;}
for (int i = 0; i < cnt; i ++) // 計(jì)算因子和
{
Co_num = 1, Co_sum = 0;
for (int j = 0; j <= num[i][1]; j ++) // 先算出 質(zhì)因子(Xi^0 + Xi^1 + Xi^2 +···+ Xi^n-1 + Xi^n) 之和
{
Co_sum += Co_num;
Co_num *= num[i][0];
}
sum *= Co_sum; // 各項(xiàng)指數(shù)和之間 相乘
}// 關(guān)鍵理解： 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;
}到了這里，關(guān)于XTU-OJ 1172-因子和的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
