문자열 수를 10진법으로 바꾸는 테크닉2 - n을 n번 이어붙인 정수

D - 88888888 (atcoder.jp)

D - 88888888

 

 

n을 n번 이어붙였을때, 그것을 998244353으로 나눈 나머지를 구하는 문제

 

숫자를 이어붙인 문제는... 한번 10진법으로 바꿔보면 해결법이 보이는 경우가 있다

 

https://deepdata.tistory.com/1235

문자열 수를 10진법으로 바꾸는 테크닉 - 배열에서 모든 가능한 순서쌍의 두 수를 이어붙여 만든

 

 

12을 12번 이어붙인다면

 

121212121212121212121212

 

그러면 12를 12번 이어붙였으니까 1을 12개 붙인 1....1(12번)에 12를 곱하면 되나?

 

라고 생각했는데 아니더라고

 

12*10^11 + 12*10^10 + ... + 12랑 같은건가?? 했는데...

 

실제로 계산기 해보니까 111111111111 * 12 = 1333333333332이기도 하네

 

그러면 분해를 해보자고

 

120000000000000000000000

    1200000000000000000000

        12000000000000000000

            120000000000000000

                1200000000000000

                  ....

                                            12

 

 

첫번째 수는 길이가 2인 12가 11번 붙어있으니까 0이 22개 붙어야겠지

 

2번째 수는 길이가 2인 12가 10번 붙어있으니까 0이 20개

 

...

 

12 * 10^22 + 12 * 10^20 + ... + 12

 

비슷하게 132를 132번 이어붙인다면??

 

132132132132....132

 

얘를 분해한다면??

 

13200000000....000                       

 

...                         

 

132

 

 

여기서 첫번째 수는? 132에다가 뒤에 길이가 3인 132가 131번 붙었겠지

 

2번째 수는 132에다가 뒤에 길이가 3인 132가 130번 붙었겠지

 

...

 

일반적으로 n을 n번 이어붙인다면??

 

n의 길이가 d일때 첫번째 수는 n에다가 길이가 d인 n이 n-1번 붙었을거니까

 

(n-1)d개의 0이 있을거고

 

2번째 수는 n에다가 길이가 d인 n이 n-2번 붙었을테니까

 

(n-2)d개의 0이 있을거고

 

...

 

$$V_{n} = n*10^{(n-1)d} + n*10^{(n-2)d} + n*10^{(n-3)d} +... +  n = n(1 + 10^{d} + 10^{2d} + ... + 10^{(n-1)d})$$

 

 

여기서 $1 + 10^{d} + 10^{2d} + ... + 10^{(n-1)d}$는 초항이 1이고 공비가 $10^{d}$이며 항 수가 n개인 등비수열의 합이다.

 

$$V_{n} = n * \frac{10^{nd} - 1}{10^{d} - 1}$$

 

$10^{d} - 1$은 998244353과 서로소이므로....

 

서로소라고 확신할 수 있나??

 

모르겠으면 n이 최대 10^18이므로 d는 1부터 19까지 가능하다. 이 경우에 대해 998244353과 나눠보면 될 것이다..

 

아무튼 페르마의 소정리를 이용하여 모듈로 곱셈의 역원을 구하고 10^nd의 경우 pow() 함수로 나머지를 구하면서 빠르게 구하면

 

n = input()

d = len(n)

n = int(n)

mod = 998244353

a = n % mod
b = pow(10**d-1,mod-2,mod)
c = (pow(10,n*d,mod) - 1) % mod

print((a*b*c) % mod)