Minimum Sum LCM(分解因子)

题目大意:给出一个n,将n分解成n = p1 ^ k1 * p2 ^ k2 * … * pm ^ km,然后求解sum = ∑(1≤i≤m)pi ^ ki.

 

解题思路:比较费解的是n本身就是素数,那么n应该分解成n^ 1 + 1 ^ 1,所以sum= n + 1,还有一种就是n = p ^ k,sum = p ^ k + 1.

 

 

[cpp][/cpp] view plaincopy

  1. #include <stdio.h>
  2. #include <math.h>
  3. int main () {
  4.     int cas = 1, n;
  5.     while (scanf(“%d”, &n), n) {
  6.         long long sum = 0, tmp = sqrt(n), cnt = 0;
  7.         for (int i = 2; i <= tmp; i++) {
  8.             if (n % i == 0) {
  9.                 int c = 1;
  10.                 cnt++;
  11.                 while (n % i == 0) {
  12.                     c *= i;
  13.                     n /= i;
  14.                 }
  15.                 sum += c;
  16.             }
  17.         }
  18.         if (n > 1 || cnt == 0) {
  19.             sum += n;
  20.             cnt++;
  21.         }
  22.         if (cnt == 1)   sum++;
  23.         printf(“Case %d: %lld\n”, cas++, sum);
  24.     }
  25.     return 0;
  26. }

标签