파이썬에서 주어진 방정식의 값을 찾는 프로그램

<시간/>

다섯 개의 정수 a, b, c, d, n이 주어졌다고 가정합니다. ((ab)(cd)) mod n을 찾아야 합니다. 출력 값은 정수입니다.

따라서 입력이 a =2, b =3, c =2, d =4, n =10이면 출력은 6이 됩니다.

2^3 = 8
2^4 = 16
8^16 = 281474976710656
281474976710656 mod 10 = 6

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

helper() 함수를 정의합니다. n
- p :=n
- i :=2
- 동안 i * i <=n, do
  - n mod i가 0과 같으면
    - p :=p - (p / i)의 하한값
  - n mod i가 0인 동안 do
    - n :=(n / i)의 하한값
  - i가 2와 같지 않으면
    - 나는 :=나는 + 2
  - 그렇지 않으면
    - 나는 :=나는 + 1
- n> 1이면
  - p :=p - (p / n)의 하한값
- 반환
b가 0과 같거나 (c가 0과 같고 d가 0과 같지 않은 경우)
- 반환(a ^ 0) 모드 n
c가 1과 같거나 d가 0과 같으면
- 반환 (a ^ b) 모드 n
a가 0과 같거나 mod n이 0과 같으면
- 0을 반환
d가 1과 같으면
- 반환 (a ^ b * c) 모드 n
p :=도우미(n)
e :=(c ^ d) 모드 p + p
return (((a ^ b) mod n) ^ e) mod n

예시

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

def helper(n):
   p = n
   i = 2
   while i * i <= n:
      if n % i == 0:
         p -= p // i
      while n % i == 0:
         n = n // i
      if i != 2:
         i += 2
      else:
         i += 1
   if n > 1:
      p -= p // n
   return p

def solve(a, b, c, d, n):
   if b == 0 or (c == 0 and d != 0):
      return pow(a, 0, n)
   if c == 1 or d == 0:
      return pow(a, b, n)
   if a == 0 or a % n == 0:
      return 0
   if d == 1:
      return pow(a, b * c, n)
   p = helper(n)
   e = pow(c, d, p) + p
   return pow(pow(a, b, n), e, n)

print(solve(2, 3, 2, 4, 10))

입력

2, 3, 2, 4, 10