일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 |
- 빅세타
- linear dependence
- python
- Big-Oh notation
- 일차변환
- 코틀린 Hello World!
- recursive algorithms
- nonhomogeneous linear system
- Big-Oh 예제
- one-to-one
- Big-O 예제
- NumPy
- matrix fo a linear transformation
- itertools
- homogeneous linear system
- 빅오 표기법
- matrix trnasformations
- trivial solution
- 페이지 겹칩
- 랜덤 순서 배열
- nontrivial solution
- 배열 섞기
- 알고리즘 분석의 실례
- 이진 탐색
- 코틀린 시작하기
- includepdf
- 재귀함수
- 빅오메가
- Big Theta
- Big Omega
- Today
- Total
코딩 연습
프로젝트 오일러 134번 본문
Consider the consecutive primes p1=19 and p2=23. It can be verified that 1219 is the smallest number such that the last digits are formed by p1 whilst also being divisible by p2.
In fact, with the exception of p1−3 and p2=5, for every pair of consecutive primes, p2>p1, there exist values of n for which the last digits are formed by p1 and n is divisible by p2. Let S be the smallest of these values of n.
Find ∑S for every pair of consecutive primes with 5≤p1≤1000000.
연속적인 소수 p1=19,p2=23 에 대하여 1219 는 다음과 같은 성질이 있다. 끝자리가 p1 으로 끝나며 1219 자체는 p2 로 나누어 떨어진다.
사실 p1=3,p2=5 을 제외한 모든 연속적인 소수 쌍 p1,p2(p2>p1) 에 대해서 끝자리가 p1 으로 끝나고, p2 로 나누어 떨어지는 자연수 n 이 존재한다. S 는 이런 n 의 최솟값이라고 한다.
5≤p1≤1000000 에 해당하는 연속적인 소수 쌍 p1,p2 에 대하여 ∑S 를 구하시오.
p1이 d 자리 자연수라고 한다면 우리가 찾는 n 은 다음과 같은 형태로 표현이 가능하다.
10d×x+p1=p2×k(단,k는정수)
10d×x=p2×k−p1
결국 10d×x 는 p2 로 나누었을 때의 나머지가 −p1 이란 뜻이 된다. 나머지를 [0,p2) 범위에서 생각하려면 10d×x=p2×k+(p2−p1) 의 형태로 바꾸면 된다. 이를 합동식으로 표현하면 다음과 같다. 10d×x≡p2−p1(modp2)
합동식 풀이법을 사용하여 위 식을 만족하는 x 를 구해내면 된다.
반드시 위 합동식 풀이법 링크를 따라가서 내용을 숙지하고 와야 한다.
이 풀이법에서 사용된 확장 유클리드 알고리즘을 나타내는 함수만 공개하도록 하겠다.
def extnded_euclidean(a, b): (fx, x) = (1, 0) (fy, y) = (0, 1) while b != 0: q = a // b temp = b b = a % b a = temp temp = x x = fx - q * x fx = temp temp = y y = fy - q * y fy = temp return fx
'project euler with python' 카테고리의 다른 글
프로젝트 오일러 136번 (0) | 2016.03.15 |
---|---|
프로젝트 오일러 135번 (0) | 2016.03.15 |
프로젝트 오일러 133번 (0) | 2016.03.15 |
프로젝트 오일러 132번 (0) | 2016.03.15 |
프로젝트 오일러 131번 (0) | 2016.03.15 |