6674. 度度熊与数字

HDOJ 6674. 度度熊与数字

2019 年百度之星·程序设计大赛 - 初赛二

• 6674. 度度熊与数字
• 6675. 度度熊与排列
• 6676. 度度熊与运算式 1

题目：6674. 度度熊与数字

问题描述：

度熊发现，1个， 3 以及 9 这三个数字很神奇，它们的所有的倍数的每位数字的和一定是自己的倍数。 54 是 3 的倍数，同时 5 + 4 = 9 也是 3 的倍数。在另一个例子 666 是 9 的倍数，同时 6 + 6 + 6 = 18 也是 9的倍数。

度熊又发现，除了1个， 3， 9 以外的正整数，虽然不一定满足“所有的倍数的每位数字的和一定是自己的倍数”，但也存在一些数是它们的倍数且各位数字和也是它们的倍数。888 是 12 的倍数，且他的各位数字和 8 + 8 + 8 = 24 也是 12的倍数。

现在度熊想知道，给你一个正整数V，是否存在一个数 X，从而 V 是 X 的倍数，同时它的每位数字的和也是 X 的倍数呢？请寻找所有这样的数 X。

输入：

有多组询问，第一行包含一个正整数 T代表有几组询问，随后每组测试数据占一行，包含一个正整数 V。
1 ≤ T≤ 100
1 ≤ V≤109

输出：

对于每一个询问，输出两行，第一行包含一个正整数 m，m 代表对于该询问的 V，有几个满足条件的 x。第二行输出 m 个数，把所有满足条件的 x 由小到大输出。

样本输入：

3
1
9
666666

样本输出：

1
1
3
1 3 9

6

1 2 3 6 9 18

注意：

第一个询问中，11 的各位数和为 1=1×1，本身等于1×1 都是 1 的倍数，故 1 确实为 V=1 的答案。

第三个询问中，666666 的各位数和为 36=9×4，本身等于9×7474 都是 99 的倍数，故 9 确实为 V=666666的答案，经过仔细计算后能发现，除 9 以外, 1,2,3,6,18 也都是答案。

方法：枚举

思路：因为1必为所求X，所以只需从2开始枚举到numberSum(V)满足V%X== 0 && numberSum(V)%X == 0的即为所求除1外的X。

运行数据：执行用时：249 MS，内存消耗：9400K

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

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int m = sc.nextInt();

        while (m-- > 0) {
            
            int v = sc.nextInt();

            StringBuilder result = new StringBuilder("1");

            int count = 1;

            int numberSum = numberSum(v);

            for (int i = 2; i <= numberSum; i++) {
                if (v % i == 0 && numberSum % i == 0) {
                    result.append(" " + i);
                    count++;
                }
            }

            System.out.println(count);
            System.out.println(result);
        }
    }
	
    // 求number各位数字之和
    public static int numberSum(int number) {

        int sum = 0;

        while (number != 0) {
            sum += number % 10;
            number /= 10;
        }

        return sum;
    }
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！