파이썬에서 좋은 제수의 수를 최대화하는 프로그램

<시간/>

우리가 pf가 소인수의 수를 나타낸다고 가정합니다. 다음 조건을 만족하는 양수 n을 만들어야 합니다. -

n의 소인수(고유할 수도 있고 아닐 수도 있음)는 최대 pf입니다.
n의 좋은 제수의 수는 최대화됩니다. 우리가 알다시피 n의 제수는 n의 모든 소인수로 나눌 수 있을 때 좋습니다.

n의 좋은 제수의 수를 찾아야 합니다. 답이 너무 크면 결과 모듈로 10^9 + 7을 반환합니다.

따라서 입력이 pf =5와 같으면 n =200의 경우 소인수 [2,2,2,5,5]가 있고 좋은 제수가 [10,20,40,50,100,200이기 때문에 출력은 6이 됩니다. ] 따라서 6의 약수입니다.

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

pf가 1과 같으면
- 1 반환
m :=10^9 + 7
q :=pf/3의 몫, r :=pf mod 3
r이 0과 같으면
- 3^q mod m
  반환
그렇지 않으면 r이 1과 같을 때
- return (3^(q-1) mod m)*4 mod m
그렇지 않으면
- return (3^q mod m)*2 mod m

예시

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

def solve(pf):
   if pf == 1:
      return 1
   m = 10** 9 + 7
   q, r = divmod(pf, 3)
   if r == 0:
      return pow(3, q, m)
   elif r == 1:
      return pow(3, q-1, m) * 4 % m
   else:
      return pow(3, q, m) * 2 % m

pf = 5
print(solve(pf))