SGU108 数学题 Math

题目：一个数n，d(n)是n的各个位之和与它本身的和，比如d(35) = 35 + 3 + 5 = 43。n成为d(n)的产生数。现在给你一个数N和K，以及K个数Sk，问1-N有多少个自我数（没有产生数），以及第Sk个自我数是多少。

Problem: For any positive integer n, define d(n) to be n plus the sum of the digits of n. For example, d(35) = 35 + 3 + 5 = 43. n is called the generator of d(n). Now give you N, K and K numbers Sk. Please answer the following two questions: 1. How many self-numbers(a number without generator) between 1-N 2. What is the Sk-th self-number

解法：我们用O(n)来一边求，一边记录，方法类似于质数筛法。考虑到空间限制，布尔数组用滚动数组。

Solution: We can calculate each number and record the answer in O(n). Considering the space limit, we use rolling array here.

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; #define N 1000 struct data { int c,id; }a[5010],b[5010]; bool f[1010]; int n,k,pnum,now,cnt; int d(int x) { int s = x; while (x) { s += x%10; x /= 10; } return s; } bool cmp1(data a, data b) { if (a.c