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.
510. 프로젝트 오일러 #510 : 원의 접선
중학수학 시절에 기하가 나오면, 보조선만 잘 그리면, 기하 문제는 왠만하면 풀린다는 것이죠. 이 문제도 역시 보조선을 잘 그리면 될거라고 생각합니다. 보조선을 그린 이미지를 보시면, 원 A에서 선 L에 수선을 내리고, 원B에서 선 L에 수선을 내리고, 원 A의 중심에서 L과 편행하고 선을 긋고, 원 C의 중심에서 L과 평행하게 선을 긋습니다. 그러면 그림과 같이 A, B, C 라는 삼각형을 얻습니다. 이 문제의 풀이는 바로 이 세개의 직각삼각형에서 출발합니다. 직각삼각형이므로 당연히 피타고라스 법칙이 성립합니다. 그런데, 삼각형 A의 밑변, 삼각형 B의 밑변, 삼각형 C의 밑변이 자연수라고 생각할 수 있는 근거가 그림상에는 전혀 없습니다. 당연히 A, B의 밑변의 합은 C의 밑변의 길이와 같다는 것은 알..
2015. 4. 22.
