[일반] 나는 E 이렇게 풀었음

[익명(119.194)]

대충 400이하 소수들 먼저 전처리해둠

c = 1~n-2 각각에 대해서

a + b = n-c

n-c를 전처리 이용해서 소인수분해, 소인수와 각 인수의 차수를 구해줌

그리고 백트래킹을 이용해서 각각의 인수를 gcd(a, b)로 둔 뒤

오일러 피함수를 이용해서 총 몇개 가능한지 gcd(a, b)별로 구함

구한 개수*lcm(gcd(a, b)*c)를 ans에 더해주는 식으로 구했음

정해인지는 모르겠는데 아닐거같음

[펜져(penzer27)]

와 오일러 피함수 ㄷㄷ 이런게 있네

[펜져(penzer27)]

근데 n-c의 인수들만 gcd로 보면 됨??

[펜져(penzer27)]

예를 들어 n - c가 15면 gcd(a, b) 가 2거나 7일 가능성이 없다? 내가 이해한게 맞나 ㄷㄷ

[익명(119.194)]

유클리드 호제법 생각해보면 gcd(a, b) = gcd(a+b, a) = gcd(n-c, a)니까 당연히 n-c의 인수여야댐

[펜져(penzer27)]

호제법 생각하면 ㄷㄷ 식으로 보면 맞는데 직관이 아직 안오네! 입체적으로 좀 더 생각해봐야겠다 ㄱㅅㄱㅅ

[펜져(penzer27)]

아 그러네 n - c 를 어떤 수 x로 나눴을 때 나머지가 생기면 이게 a던 b던 포함되면 x로는 a혹은 b가 나눠 떨어지지 않는게 보장 되는구만

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[펜져(penzer27)]

https://youtu.be/96OEN2c28So
다른 사람들을 위한 euler phi함수 강의 링크

[익명(119.194)]

phi((n-c)/gcd) 요거임

[펜져(penzer27)]

와 이해도 미쳤다 ㄷㄷ 수학 진짜 잘하는 분인듯 감삼돠

[펜져(penzer27)]

아 저거 폰으로 노트 그적이다가 잘 못 눌러서 삭제됨..

[펜져(penzer27)]

선생님께 gcd 별로 총 개수 구하려면 피함수 어떻게 활용해야 되는지에 대한 질문이었음.

[익명(61.255)]

내가 이렇게 짜다가 시간 부족해서 못품 ㅠ

[익명(119.194)]

이게 정해였네