UVA 10042 Smith Numbers

brute-force uva

不停地比較. 錯的就加一, 直到找到答案. 只要算sum of factor的那一部份正確就過了.

uva10042.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <cmath>

int sum_of_digit(int v) {
    int sum = 0;
    while(v > 0) {
        sum += v%10;
        v /= 10;
    }
    return sum;
}

int sum_of_factor(int v) {
    if(v == 0) return 0;
    if(v == 1) return 2;

    int sum = 0;
    int remain = v;

    int limit = sqrt(v) + 1;
    int count = 0;

    while(remain % 2 == 0) {
        remain /= 2;
        sum += 2;
        count++;
    }

    for(int i = 3; i <= limit; i += 2) {
        while(remain % i == 0) {
            remain /= i;
            sum += sum_of_digit(i);
            count++;
        }
    }

    if(count == 1 || (count > 1 && remain != 1)) sum += sum_of_digit(remain);
    if(count == 0) sum += 1 + sum_of_digit(v);
    return sum;
}

int main() {
    int ncase,v;
    scanf("%d", &ncase);

    for(;ncase > 0; --ncase) {
        scanf("%d", &v);
        int vv = v + 1;
        while(sum_of_digit(vv) != sum_of_factor(vv))
            vv++;
        printf("%d\n", vv);
    }

    return 0;
}