CFR 795 E. Big Number and Remainder ( Math )
題意:
給大數 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 )