HDU6674度度熊与数字(水题)

Problem Description

度熊发现，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。

Input

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

Output

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

Sample Input

3

1

9

666666

Sample Output

1

1

3

1 3 9

6

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

题意 : 给定一个数字V, 要求搜索一个数字X (X可能有多个, 从小到大输出即可), 要求V%X == 0 && sum(X)%X == 0   (sum(X) 为X每位数字之和)

思路: 从1开始枚举到sum(X)   满足V%X == 0 && sum(X)%X == 0即可 (不能从1枚举到V, V太大了)

如果有更好的解法, 请务必教我, 蒟蒻感激不尽!!!!!!!

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <set>
#include <algorithm>
#define min(x,y) ( x > y ? y : x )
#define ll long long int
#define MAXN 10005
using namespace std;

int t, v;

int sumit(int a) {
    int rs = 0;
    while(a) {
        rs += a%10;
        a /= 10;
    }
    return rs;
}

bool check(int a, int b, int mod) {
    return a%mod == 0 && b%mod == 0;
}

int main(void) {
    //freopen("test", "r", stdin);
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &v);
        set<int> seta;
        int sum = sumit(v);
        for(int i=1; i<=sum; i++) {
            if(check(sum, v, i)) seta.insert(i);
        }
        set<int>::iterator it = seta.begin();
        printf("%d\n", seta.size());
        while(it != seta.end()) {
            if(it != seta.begin()) printf(" ");
            printf("%d", *it);
            it ++;
        }
        printf("\n");
    }
    return 0;
}