c++ - 找到第 N 个最小的整数

Question

一个整数如果大于0且其十进制表示的各位数字之和是10的倍数，则为整数。求第N小的整数。

1≤N≤10^18

我已经尝试过这种天真的方法，但该解决方案不适用于大约束。

#include <bits/stdc++.h> 
 using namespace std; 

 int sumOfDigits(int n) 
 { 
  int sum = 0; 
  while (n > 0) { 
    sum += n % 10; 
    n /= 10; 
   } 

    return sum; 
 } 

 int findNum(int n) 
 { 
   int c=0, num=0;

    while (c != n) { 
    num++; 
    int sum = sumOfDigits(num); 
    if (sum % 10 == 0) 
        c++; 
 } 

  return num; 
 } 

 int main() 
{ 
 int t, n;
 cin>>t;
 while(t--){
    cin>>n;
    cout<<findNum(n)<<endl;
 }
 } 

有什么好的方法可以解决这个问题。请不要粘贴整个解决方案，我只想要解决此问题的方法。

我也尝试过另一种方法..但解决方案效果不佳。

  public static long findNth(int n) 
  { 
    long nthElement = 19 + (n - 1) * 9; 
    int outliersCount = (int)Math.log10(nthElement) - 1; 

    nthElement += 9 * outliersCount; 
    return nthElement; 
  } 

会有数列形式:19、28、37、46、55、64……但记得去掉100、1000……等等。

考虑到这一点，我尝试了上面的解决方案，但它不起作用。

我正在使用其中一种已回答的方法。但这也不太好..

int sumOfDigits(int n) 
{ 
int sum = 0; 
while (n > 0) { 
    sum += n % 10; 
    n /= 10; 
} 
if(sum%10==0) return 0;
else if(sum<10) return 10-sum;
return 10-sum%10;
} 

long long findNum(int n) 
{ 
return n*10+sumOfDigits(n);
} 

Answer 1

一个重要提示:如果一个n位整数的前n-1位是固定的，则恰好存在一个数字可以作为最后一位满足条件。也就是说，每10个整数(从10开始)，正好有一个整数满足要求的条件。基于此有一个非常简单的解决方案，直接生成答案而不是一个一个地枚举整数并验证条件。