Subscribed unsubscribe Subscribe Subscribe

0w1

CFR 795 E. Big Number and Remainder ( Math )

Problem - E - Codeforces

題意:
給大數 N,以及一個數字 M。考慮 N 的所有循環 ( N[ x : ] + N[ : x ], for any N[ x ] != 0 ),問其中模 M 後最小的數字為何。

制約:
The first line contains the integer which Stepan has. The length of Stepan's integer is between 2 and 200 000 digits, inclusive. It is guaranteed that Stepan's integer does not contain leading zeros.
The second line contains the integer m (2 ≤ m ≤ 1e8) — the number by which Stepan divides good shifts of his integer.

解法:
求一次 N % M,接著由左至右依序將頭捨去並接到尾。

N = input()
M = int( input() )
cur = int( N ) % M
ans = cur
for i in range( len( N ) ):
  cur -= ( ord( N[ i ] ) - ord( '0' ) ) * pow( 10, len( N ) - 1, M ) % M
  cur = cur * 10 % M
  cur = ( cur + ord( N[ i ] ) - ord( '0' ) ) % M
  if N[ ( i + 1 ) % len( N ) ] != '0':
    ans = min( ans, cur )
print( ans )