c - 可被n整除的最小正整数

对于给定的数n，求可被n整除的最小正整数，其位数之和等于n。
我找了很多，也得到了一些答案，但这些对我来说并不容易理解。我是个新程序员，喜欢用C语言编程。所以如果有人帮我在C语言中找到解决这个问题的方法，我会很高兴的。
我曾经尝试过，但我的代码不适用于n的大输入，所以n=999。
我的代码如下：

#include <stdio.h>
#include <stdlib.h>
long long int summingDigit(long long int dividend);

int main()
{
    long long int n, dividend, add, ans;
    int i, test, c;
    scanf("%d", &test);
    for(c=1; c<=test; c++) {
    scanf("%lld", &n);
    for(i=1; ; i++) {
        dividend = n*i;
        add = summingDigit(dividend);
        if(add==n) {
            ans=dividend;
            break;
        }
    }
    printf("%lld\n", dividend);
    }
    return 0;
    }


long long int summingDigit(long long int dividend)
{
    long long int sum=0, rem;
    while(dividend!=0) {
        rem=dividend%10;
        dividend=dividend/10;
        sum=sum+rem;
    }
    return sum;
}

实际上我希望结果是：
对于n=1，结果=1
对于n=10，结果=190
解释结果包含3位数字它们的和1+9+0=10等于n（10）希望大家都能理解。
请给我一个省时的好方法。因为我的解决方案需要太多时间但我不能理解其他编程语言。所以，请用C语言简单地解释一下。谢谢你在高级阶段帮我。
我找到了解决办法，但不明白。如果你有足够的时间，请允许我理解整个程序。

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define F first
#define S second
#define N 1100
#define mp make_pair
queue<pair<int, int> >Q;
short sumTrace[N][N], mulTrace[N][N];

void print(int sum, int mul)
{
    if (sumTrace[sum][mul] == 42)return;
    print(sum-sumTrace[sum][mul], mulTrace[sum][mul]);
    printf("%d",sumTrace[sum][mul]);
}
void solve(int n)
{
    Q.push(mp(0,0));
    sumTrace[0][0]=42; // any number greater than 9
    while (1)
    {
        int sum = Q.front().F;
        int mul = Q.front().S;
        if (sum == n && mul == 0) break;
        Q.pop();
        for (int i=0; i<10; i++)
        {
            int nsum = sum+i;
            if (nsum > n)break;
            int nmul = (mul*10+i)%n;
            if (sumTrace[nsum][nmul] == -1)
            {
                Q.push(mp(nsum, nmul));
                sumTrace[nsum][nmul] = i;
                mulTrace[nsum][nmul] = mul;
            }
        }
    }
    print(n,0);
    while(!Q.empty())Q.pop();
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        memset(sumTrace, -1, sizeof sumTrace);
        solve(n);
        printf("\n");
    }
    return 0;
}

最佳答案

一个可能的小优化如下：
你可以在这里用点数学。
如果存在i使得n*i的数字之和为n，则：

Say n*i = p + 10q + 100r + 1000s +... (where p, q, r, s are digits of n*i)
Then p + q + r + s ... = n.

Hence n * (i-1) = 9q + 99r + 999s +... (after subtracting n from both sides)
                = 9 * (q + 11r + 111s +... )

因此你注意到n*（i-1）总是9的倍数。
因此，如果n最初不是9的倍数，那么可以通过采取9（i += 9）而不是1（i++）的步骤跳过许多可能的候选项。
你可以根据这些思路思考，你可能会想出更好的办法。

关于c - 可被n整除的最小正整数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23956688/