题目145：10亿以下有多少可反数？

欧拉计划

How many reversible numbers are there below one-billion?

Some positive integers n have the property that the sum [ n + reverse(n) ] consists entirely of odd (decimal) digits. For instance, 36 + 63 = 99 and 409 + 904 = 1313. We will call such numbers reversible; so 36, 63, 409, and 904 are reversible. Leading zeroes are not allowed in either n or reverse(n).

There are 120 reversible numbers below one-thousand.

How many reversible numbers are there below one-billion (10⁹)?

题目：

一些正整数 n 有这样一个性质：n 与 n取“相反”之和的所有位皆为奇数。例如： 36 + 63 = 99 以及 409 + 904 = 1313。我们将这样的数成为可反数；所以，36，63，409，904 都是可反数。在 n 和 n 取相反的最前面都不允许有 0。

一千以下共有 120 个可反数。

10 亿（10⁹）以下共有多少个可反数？

迷雾少年

608720个吧
跑了我好久的说

1. #include <myLib/myLib.h>
   
2. 
   
3. 
   
4. //判断是否为可反数
   
5. bool isz(int z)
   
6. {
   
7.         char buf[10]={0};
   
8.         char b[10]={0},c[10]={0};
   
9.         itoa(z,buf,10);
   
10.         int len = strlen(buf);
    
11.          memcpy(b,buf,len);
    
12.          memcpy(c,buf,len);
    
13.          ;//c是反过来的数  b是没反的
    
14.         reverse(c,c+len);
    
15.         if(c[0]=='0') return false;
    
16.        
    
17.         //2个数字的和
    
18.         int value = atoi(b) + atoi(c);
    
19. 
    
20.     while (value)
    
21.     {
    
22.                 if((value%10)%2==0)
    
23.                         return false;
    
24.                 value/=10;
    
25.     }
    
26. 
    
27.         return true;///*******************
    
28. }
    
29. int main()
    
30. {
    
31.         int m = 0;
    
32.          
    
33.         //10亿 干 2^31 = 2147483648
    
34.         //10Y          = 1000000000
    
35.         for (int z = 1;z<=1000000000;z++)
    
36.         {
    
37.                 if(isz(z))
    
38.                 {
    
39.                         m++;
    
40.                         //std::cout<<z<<endl;
    
41.                 }
    
42.         }
    
43.         std::cout<<m;
    
44.         return 0;
    
45. }

复制代码

jerryxjr1220

1. from numba import jit, autojit
   
2. from math import log10
   
3. from time import process_time
   
4. 
   
5. @jit("int32(int32)")
   
6. def reverse_add(n):
   
7.         m = n
   
8.         l = int(log10(n))
   
9.         s = 0
   
10.         for i in range(l+1):
    
11.                 s = s*10 + n%10
    
12.                 n //= 10
    
13.         return s+m
    
14. 
    
15. @jit("boolean(int32)")
    
16. def judge_odd(n):
    
17.         while n > 0:
    
18.                 if n % 2 == 0:
    
19.                         return False
    
20.                 n //= 10
    
21.         return True
    
22. 
    
23. @jit("int32(int32)")
    
24. def solve(limit):
    
25.         c, i = 0, 11
    
26.         while i < limit:
    
27.                 if (i // (10**int(log10(i)))) % 2:
    
28.                         i += 10**int(log10(i))
    
29.                 if judge_odd(reverse_add(i)):
    
30.                         c += 2
    
31.                 i += 2
    
32.         return c
    
33. 
    
34. print(solve(1000000000))
    
35. print(process_time())

复制代码

608720

永恒的蓝色梦想

1. #include<stdio.h>
   
2. 
   
3. 
   
4. bool isreversible(int n) {
   
5.     if (!(n % 10)) {
   
6.         return false;
   
7.     }
   
8. 
   
9.     int temp = n, res = 0;
   
10. 
    
11.     while (temp) {
    
12.         res = res * 10 + temp % 10;
    
13.         temp /= 10;
    
14.     }
    
15. 
    
16.     res += n;
    
17. 
    
18.     while (res) {
    
19.         if (!(res & 1)) {
    
20.             return false;
    
21.         }
    
22.         res /= 10;
    
23.     }
    
24. 
    
25.     return true;
    
26. }
    
27. 
    
28. 
    
29. int main() {
    
30.     int sum = 0;
    
31.     for (int i = 1000000000; --i; sum += isreversible(i));
    
32.     printf("%d", sum);
    
33.     return 0;
    
34. }

复制代码

guosl

/*
608720
1.48196秒 (AMD R5 5600G)
*/
#include <iostream>
#include <omp.h>
using namespace std;

int main(void)
{
  double t = omp_get_wtime();
  int nCount = 0;
#pragma omp parallel for reduction(+:nCount)
  for (long long i = 11; i < 1000000000ll; ++i)
  {
    if (i % 10 == 0)
      continue;
    long long k = i, j = 0;
    while (k != 0)
    {
      j = 10 * j + k % 10;
      k /= 10;
    }
    k = i + j;
    bool bFlag = true;
    while (k != 0)
    {
      if (((k % 10) & 1) == 0)
      {
        bFlag = false;
        break;
      }
      k /= 10;
    }
    if (bFlag)
      ++nCount;
  }
  t = omp_get_wtime() - t;
  cout << nCount << endl << t << endl;
  return 0;
}