有关给定数量n找到的最小的正整数被n整除，以数字等于n的总和。

我寻觅了很多，也得到了一些回答这个问题，但这些都不是容易理解我。我是一个新的程序员，喜欢code在C编程语言。这就是为什么我会很高兴，如果有人帮我找到这个C.问题的解决 我怎么没有试过，我的code不工作对n的大投入。使得n = 999。 我的code放在这里：

 的#include＆LT; stdio.h中＆GT;
＃包括＆LT; stdlib.h中＆GT;
得到long long int summingDigit（长的长整型股息）;

诠释的main（）
{
    得到long long int N，红利，加，答;
    INT I，测试，C;
    scanf函数（％d个，和放大器;测试）;
    为（C = 1; C＆LT; =测试; C ++）{
    scanf函数（％LLD，和放大器; N）;
    对于（i = 1;我++）{
        分红= N * I;
        添加= summingDigit（股息）;
        如果（添加== N）{
            ANS =股息;
            打破;
        }
    }
    的printf（％LLD \ N，红利）;
    }
    返回0;
    }


得到long long int summingDigit（长的长整型分红）
{
    得到long long int总和= 0，REM;
    而（分红！= 0）{
        REM =股息10％;
        股息红利= / 10;
        总和=总和+ REM;
    }
    返回总和;
}
 

其实我希望的结果： 对于n = 1，结果= 1 对于n = 10，结果= 190 对于解释结果包含3个数字。和它们的和1 + 9 + 0 = 10，它是等于n（10）。希望所有人都能够理解。

请给我节省时间这个问题的一个更好的办法。因为我的解决方案将花费太多时间。但我无法理解别人的编程语言。因此，请在C中解释这一点很容易。感谢您帮助我先进。

我已经找到一个解决方案，但不明白。请允许我了解完整的程序，如果你有足够的时间。

 ＃包括＆LT; cstdio＆GT;
＃包括＆LT;排队＆GT;
＃包括＆LT; CString的GT;
使用名字空间std;
＃定义F的第一
＃定义第二
＃定义ñ1100
＃定义MP make_pair
队列＆LT;对＆LT; INT，INT＆GT; ＆GT;问;
短sumTrace [N] [N]，mulTrace [N] [N];

无效打印（INT总和，INT MUL）
{
    如果（sumTrace [总和] [MUL] == 42）回报;
    打印（和 -  sumTrace [总和] [MUL]，mulTrace [总和] [MUL]）;
    的printf（％D，sumTrace [总和] [MUL]）;
}
解决无效（INT N）
{
    Q.push（MP（0,0））;
    sumTrace [0] [0] = 42; //任何数目大于9
    而（1）
    {
        INT总和= Q.front（）F。
        INT MUL = Q.front（）S。
        如果（总和== N'放大器;＆安培; MUL == 0）破;
        Q.pop（）;
        的for（int i = 0;我小于10;我++）
        {
            INT nsum =总和+我;
            如果（nsum＆GT; N）打破;
            INT nmul =（MUL * 10 + I）％N;
            如果（sumTrace [nsum] [nmul] == -1）
            {
                Q.push（MP（nsum，nmul））;
                sumTrace [nsum] [nmul] =我;
                mulTrace [nsum] [nmul] = MUL;
            }
        }
    }
    打印（N，0）;
    而Q.pop（）（Q.empty（）！）;
}

诠释的main（）
{
    INT吨;
    scanf函数（％d个，＆amp; T公司）;
    而（T--）
    {
        INT N;
        scanf函数（％d个，和放大器; N）;
        memset的（sumTrace，-1，sizeof的sumTrace）;
        解决（N）;
        的printf（\ N）;
    }
    返回0;
}
 

解决方案

可能一个小小的优化可以如下：

您可以使用一点数学这里。

如果存在一个我这样的数字N *我是 N ，那么：

 说N * I = P + 10Q + 100R + 1000 + ...（其中，P，Q，R，S是N *我位数）
然后P + Q + R + S ... = N。

因此N *第（i-1）= 9Q + 99R + 999S + ...（从两侧减去Ñ之后）
                = 9 *（Q + 11R + 111S + ...）
 

因此，你注意到N *（I-1）应始终的倍数9

因此​​，如果n是本来不是9的倍数，那么你可以跳过很多可能的候选人采取步骤9（ + = 9 I）而不是1（我++ ）。

您可以把这些线，你可以拿出更好的东西。

For the given number n find the minimal positive integer divisible by n, with the sum of digits equal to n.

I have searched a lot and also got some answer to this question but those are not easy to understand for me. I'm a new programmer and like to code in C programming language. That's why I will be happy if anyone help me to find the solution of this problem in C. How ever I've tried and my code isn't working for large input of n. such that n=999. My code goes here:

#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;
}

Actually I'm wishing the result: for n=1, result=1 for n=10, result=190 For explanation result contains 3 digits. and their sum 1+9+0 = 10 which is equal to n(10). Hope all are able to understand.

Please give me a better way for time saving of this problem. Cause my solution will take too much time. But I'm unable to understand others programming language. So, please explain this in C easily. Thanks for helping me in advanced.

I have find a solution but don't understand. Please allow me to understand the full program if you have enough time.

#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;
}

One small possible optimization can be as follows:

You can use a bit of math here.

If there exists an i such that the sum of digits of n*i is n, then:

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 +... )

Hence you notice that n*(i-1) shall always be a multiple of 9.

So if n is originally not a multiple of 9, then you can skip many possible candidates by taking steps of 9 (i += 9) instead of 1 (i++).

You can think on these lines and you may come up with something better.