0w1

Yuki 491 10^9+1と回文 ( Ad hoc, Palindrome )

No.491 10^9+1と回文 - yukicoder

題意:
給 N,問有幾個數字不超過 N,是 1e9 + 1 的倍數,並且是迴文。

制約:
N ≤ 1e18

解法:
怒猜超過 1e9 之後不會有迴文了。( 求證明 )
所以要求的其實是 1e9 以下的迴文數。
因為是迴文,所以只要枚舉左半邊,也就是大約 1e4.5。

時間 / 空間複雜度:
O( N^0.25 )

N = int( input() )
ans = 0
for i in range( 1, 10, 1 ):
  if i * int( 1e9 + 1 ) <= N:
    ans += 1
for i in range( 1, int( 1e5 ), 1 ):
  f = int( str( i ) + str( i )[ : : -1 ] )
  if f * int( 1e9 + 1 ) > N: break
  ans += 1
  for j in range( 0, 10, 1 ):
    f = int( str( i ) + str( j ) + str( i )[ : : -1 ] )
    if f * int( 1e9 + 1 ) > N: break
    ans += 1
print( ans )