파이썬에서 n개의 1을 m으로 나눈 나머지를 구하는 프로그램

두 개의 숫자 n과 m이 있다고 가정합니다. n개의 1을 m으로 나눈 나머지를 구해야 합니다.

따라서 입력이 n =4 m =27과 같으면 1111 mod 27 =4이므로 출력은 4가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

util() 함수를 정의합니다. x, n, m

• y :=1
• n> 0일 때 수행
  • n이 홀수이면
    • y :=(y * x) 모드 m
  • x :=(x * x) 모드 m
    • n :=n/2의 바닥
• 반환 y

(util(10, n, 9 * m) / 9)

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

def util(x, n, m) :
   y = 1
   while n > 0 :
      if n & 1 :
         y = (y * x) % m
      x = (x * x) % m
      n >>= 1
   return y

def solve(n, m):
   return util(10, n, 9 * m) // 9

n = 4
m = 27
print(solve(n, m))

입력

4, 27

출력

4