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.
[C/C++] 프로젝트 오일러 #40 : 챔퍼나운 수
문제 요약 챔퍼나운 수는 0.123456789101112131415… 와 같이 자연수를 차례대로 이어붙여서 만든 무리수입니다. 문제에서는 이 상수에서 특정 위치에 있는 숫자들을 찾아 곱한 값을 구하는 것이 요구됩니다. 예를 들어, 소수점 아래 1번째 자리의 숫자는 1, 2번째는 2, 10번째는 1과 같이 특정 위치에서 숫자를 확인할 수 있습니다. 이러한 방식으로 문제에서 요구하는 여러 개의 특정 위치에 있는 숫자들을 추출하고, 이들을 곱하여 최종적으로 그 값을 도출해야 합니다.챔퍼나운수는 수론에서 무리수이자 초월수인 상수를 정의한 것입니다. 십진법이라면, 1, 2, 3, 4, 5, ... 를 세듯이 소수점 이하에 배열을 한 것입니다. 10진법 챔퍼나운 수는 다음과 같습니다.\[ C_{10} = 0.123..
2015. 4. 21.
