본문 바로가기

Project Euler #5151

515. 프로젝트 오일러 #515 : 불협화음 숫자들 문제 : Let d(p,n,0) be the multiplicative inverse of n modulo prime p, defined as n × d(p,n,0) = 1 mod p. Let for k ≥ 1.Let for all primes a ≤ p = 0 ) { int64_t r = t; t = -t*rec[count]+s; s = r; } t = (t>0)?t:p+t; return t; } 사실 인터넷에 뒤져보면, 아마 역원 구하는 알고리즘이 나와있을 것 같은데, 저는 알고리즘을 수학적 방법으로 제가 알고 있는 그대로를 구현했기 때문에 성능은 보장하지 못 합니다. 그리고 오버플로우가 발생할 수도 있고요. 이렇게 하면, 역원을 구하는 것과 d(p, n, 0)의 갯수를 세는 것이 다 되었습니다.그런.. 2015. 5. 12.
728x90

티스토리툴바