欢迎来到飞鸟慕鱼博客,开始您的技术之旅!
当前位置: 首页知识笔记正文

XTUOJ 1172因子和,牛碱性成纤维细胞生长因子凝胶

终极管理员 知识笔记 110阅读
题目描述

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

输入

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

输出

每行输出一个结果。

样例输入
12340
样例输出
1347

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

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

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

质因数之和就等于   (a^0 ) * (b^0 b^1 ···· b^x) * (c^0 c^1 ···· c^x) * ·····。

AC代码

#include <stdio.h>int main(){    int n,cnt,t;    __int64 sum,ans;    int num[50]  {0};    while (scanf(%d,&n) ! EOF && n ! 0)     {        cnt  0; sum  ans  t  1;         for (int i2; i*i<n; i)         {            for (int j0; n%i0; j)          // 找到所有的质因数,并保存            {                n/i;                num[cnt]  i;            }        }        if (n ! 1)    num[cnt]  n;        for (int i  1; i < cnt; i )         {            if (num[i] ! num[i-1])   // 如果相邻的质因数不一样,重新计算从a 跳到 b            {                sum * t;                ans  t  1;            }            t  t  ans*num[i];       // 计算同一质因数,并求和 (a^0  )            ans * num[i];        }        sum * t;                     // 最后要补充一步思考下为什么。           printf(%I64d\n,sum);    }    return 0;}

标签:
声明:无特别说明,转载请标明本文来源!