[Python] 32228번 등차수열 만들기

https://www.acmicpc.net/problem/32228

---

 

24/09/15

 

 

맷코컵 당시 검수했던 문제 중 하나이다. 알면 보자마자 떠오르는 낚시 문제다.

---

 

문제 접근 방식:

 

 

문제에서는 주저리 주저리 적혀져 있는데, 오일러 파이 함수의 값을 출력하면 끝이다.

 

그러면, 결론이 왜 그렇게 나오는지에 대해 알아야 한다.

 

문제에서 주어진 것 처럼 mod $M$에서의 등차수열을 직접 구하는 방식으로 $K$값을 짜내려고 한다면 곤란하다.

 

$N$의 제한과 $M$의 제한이 꽤나 크기 때문이다.

 

$A_i$와 $M$이 서로소라는 조건, 모두 같은 $K$제곱을 하여 $A_{i}^{K}$로 만들고 mod $M$과 엮는다는 점을 유의깊게 생각하면 쉽게 파악할 수 있다.

 

이 $K$의 값이 $\varphi (M)$이 된다면, $A_{i}^{K}$의 값이 mod $M$에 대하여 모두 $1$이 되므로, 공차가 $0$인 등차수열이 된다.

 

낚시에 낚이지 않는다면 금방 해결할 수 있을 것이다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# subtask-2
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
def prime_factorization(N): 
    prime_li = []
    k = int(N**.5)+1
    for i in range(2, k+1):
        if N % i == 0:
            while N % i == 0:
                N //= i
                prime_li.append(i)
    if N != 1:
        prime_li.append(N)
    return prime_li
def euler_phi(N):
    if N == 1:
        return 1
    prime_factor_li = prime_factorization(N)
    k = 1
    total = 1
    for i in range(1, len(prime_factor_li)):
        if prime_factor_li[i] != prime_factor_li[i-1]:
            p = prime_factor_li[i-1]
            total *= p**(k-1)
            total *= (p-1)
            k = 1
        else:
            k += 1
    p = prime_factor_li[-1]
    total *= p**(k-1)
    total *= (p-1)
    return total
print(euler_phi(M))