숫자 A가 있다고 가정합니다. A를 n번 연속으로 연결하여 큰 숫자 X를 생성하고 X 모듈로 m의 값을 찾아야 합니다.
따라서 입력이 A =15 n =3 m =8과 같으면 x가 151515이고 151515 mod 8 =3이 되기 때문에 출력은 3이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- A가 0과 같으면
- 0을 반환
- an:=A
- c:=A의 자릿수
- c:=10^c
- d:=c-1
- newmod :=d*m
- val :=(c ^ n mod newmod) -1
- val :=(val + newmod) 모드 newmod
- an :=(an * val) 모드 newmod
- 반환 층(an / d)
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(A, n, m):A ==0인 경우:0 반환 an=A c=len(str(A)) c=10**c d=c-1 newmod =d*m val =pow(c,n,newmod)-1 val =(val+newmod) % newmod an =(an*val) % newmod return an // dA =15n =3m =8print(solve(A, n, m))입력
15, 3, 8출력
3