最小的正数整除为N [英] minimal positive number divisible to N

问题描述

1 LT; = N＆LT; = 1000

1<=N<=1000

如何找到的最小的正数，即整除N，并且其位数之和应等于N

How to find the minimal positive number, that is divisible by N, and its digit sum should be equal to N.

例如：
N：结果
1：1
10：190

For example:
N:Result
1:1
10:190

和算法不应该超过2秒。

And the algorithm shouldn't take more than 2 seconds.

任何想法（伪code，PASCAL，C ++或Java）？

Any ideas(Pseudocode,pascal,c++ or java) ?

推荐答案

设f（LEN，总之，MOD）是一个布尔值，这意味着我们可以建立一个数字（可能与前导零），已长LEN + 1，数字之和等于总结和n给出mod潜水时。

Let f(len, sum, mod) be a bool, meaning we can build a number(maybe with leading zeros), that has length len+1, sum of digits equal to sum and gives mod when diving by n.

则f（LEN，总之，MOD）=或（f（LEN-1，总和 - 我的，模块I * 10 ^ LEN），因为我从0到9）。然后你就可以找到最小的L，即F（L，N，n）为真。之后，只要找到第一个数字，然后第二个，等等。

Then f(len, sum, mod) = or (f(len-1, sum-i, mod- i*10^len), for i from 0 to 9). Then you can find minimal l, that f(l, n, n) is true. After that just find first digit, then second and so on.

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, N) FOR(i, 0, N)

#define FILL(a,v) memset(a,v,sizeof(a))



const int maxlen = 120;
const int maxn = 1000;

int st[maxlen];
int n;

bool can[maxlen][maxn+1][maxn+1];
bool was[maxlen][maxn+1][maxn+1];

bool f(int l, int s, int m)
{
    m = m%n;
    if(m<0)
        m += n;

    if(s == 0)
        return (m == 0);
    if(s<0)
        return false;
    if(l<0)
        return false;   

    if(was[l][s][m])
        return can[l][s][m];

    was[l][s][m] = true;
    can[l][s][m] = false;

    REP(i,10)
        if(f(l-1, s-i, m - st[l]*i))
        {
            can[l][s][m] = true;
            return true;
        }
    return false;
}


string build(int l, int s, int m)
{
    if(l<0)
        return "";
    m = m%n;
    if(m<0)
        m += n;
    REP(i,10)
        if(f(l-1, s-i, m - st[l]*i))
        {
            return char('0'+i) + build(l-1, s-i, m - st[l]*i);
        }
    return "";
}

int main(int argc, char** argv)
{
    ios_base::sync_with_stdio(false);

    cin>>n;
    FILL(was, false);   
    st[0] = 1;
    FOR(i, 1, maxlen)
        st[i] = (st[i-1]*10)%n;
    int l = -1;
    REP(i, maxlen)
        if(f(i, n, n))
        {
            cout<<build(i,n,n)<<endl;
            break;
        }

    return 0;
}

注意，这里使用〜250 MB的内存。

NOTE that this uses ~250 mb of memory.

修改：我发现在那里这个解决方案运行，有点太长了测试。 999，差不多需要5秒。

EDIT: I found a test where this solution runs, a bit too long. 999, takes almost 5s.

这篇关于最小的正数整除为N的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！