Yuki 491 10^9+1と回文 ( Ad hoc, Palindrome )
題意:
給 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 )