SGU 108 Self-numbers 2 

---

 

Mean: 

略有这样一种数字：对于任意正整数n，定义d(n)为n加上n的各个位上的数字（d是数字的意思，Kaprekar发明的一个术语）。如：d(75) = 75 + 7 + 5 = 87。给定任意正整数n，你可以构建出无限的整数递增：n, d(n), d(d(n)), d(d(d(n))), ……举个例子，你从33开始，那么下一个数就是33 + 3 + 3 = 39, 再下一个就是39 + 3 + 9 = 51, 接着就是 51 + 5 + 1 = 57, 那样就生成了一个序列： 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ... 这里n叫做d(n)的母数 上面的数列中，33是39的母数，39是51的母数，51是57的母数，以此类推……有些数字不止一个母数，比如101有两个母数，91和100。没有母数的数字就叫做self-number。让a[i]成为第i个self-number。现在存在13个小于100的self-number： 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 和 97. (第一个 self-number是a[1]=1, 第二个是 a[2] = 3,  第十三个是 a[13]=97).

analyse:

此题比较BT，内存卡得比较紧，做的时候需要考虑如何压缩内存,不过还是1.5s把它过了.

主要方法就是用个滚动数组用类似筛法做,题目倒不是很难.

Time complexity: O(N)

 

view code

/**

* -----------------------------------------------------------------

* Copyright (c) 2016 crazyacking.All rights reserved.

* -----------------------------------------------------------------

*       Author: crazyacking

*       Date  : 2016-01-06-19.55

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using

namespace

std;

typedef

long

long(

LL);

typedef

unsigned

long

long(

ULL);

const

double

eps(

1e-8);

pair

<

int

,

int

>

q

[

5010

];

bool

f1

[

64

],

f2

[

64

];

int

ans

[

5010

];

int

num

,n

,

m;

int

main()

{

   

scanf(

"%d %d"

,

&n

,

&

m);

   

for (

int

i

=

0;

i

<

m;

++

i)

   

{

       

scanf(

"%d"

,

&

q

[

i

].

first);

       

q

[

i

].

second

=

i;

   

}

   

sort(

q

,

q

+

m);

   

int

pos

=

0;

   

memset(

f1

,

true

,

sizeof(

f1));

   

memset(

f2

,

true

,

sizeof(

f2));

   

for (

int

i

=

1;

i

<=n;

++

i)

   

{

       

if (

i

%

64

==

0)

       

{

           

memcpy(

f1

,

f2

,

64);

           

memset(

f2

,

true

,

sizeof(

f2));

       

}

       

if (

f1

[

i

%

64

])

       

{

           

num

++;

           

while (

q

[

pos

].

first

==

num)

ans

[

q

[

pos

++

].

second

]

=

i;

       

}

       

int

tmp

=

0

,

j

=

i;

       

while (

j

>

0)

       

{

           

tmp

+=

j

%

10;

           

j

/=

10;

       

}

       

if (

tmp

+

i

%

64

>=

64)

f2

[(

tmp

+

i

%

64)

%

64

]

=

false;

       

else

f1

[

tmp

+

i

%

64

]

=

false;

   

}

   

printf(

"%d

\n

"

,

num);

   

for (

int

i

=

0

,

j;

i

<

m;

++

i)

   

{

       

printf(

"%d"

,

ans

[

i

]);

       

if (

i

!=

m

-

1)

printf(

" ");

       

else

printf(

"

\n

");

   

}

   

return

0;

}