본문 바로가기

나머지연산

(10)
[EP 048] ∑ i^i (i=1 ~ 1000) 의 마지막 10자리수 구하기 #!/usr/bin/python ############################################################################ # # Problem 48 # 18 July 2003 # 1 2 3 10 # The series, 1 + 2 + 3 + ... + 10 = 10405071317. # # Find the last ten digits of the series, # 1 2 3 1000 # 1 + 2 + 3 + ... + 1000 . ############################################################################ # Author : DwYoon # Date : 2007 04 12 def pow_mod(b..
pow(a, n) for n is large def pow(a, n):k = 1a_pow_k = aa_pow_n = 1while n:if k & n:a_pow_n *= a_pow_kn -= ka_pow_k = a_pow_k ** 2k *= 2return a_pow_n an = aklmno = ak0000 al000 am00 an0 ao 위 식에서 klmno 는 n의 2진수 표현. 즉, a2k 들의 곱만으로 an 을 쪼갤 수 있고,a2k 는 a2k-1의 제곱이므로, 위 함수와 같이 빠르게 an 을 구할 수 있다. 위 함수는 변형하여 an의 나머지 연산 값을 구할 때 유용할 수 있겠다.
[Euler Project 134] 1219는 소수 19로 끝나는 23의 배수 5가 아닌 소수의 배수는 마지막 자리수가 1, ... , 9 까지 모두 나온다.
[JAVA] 원탁에서 n 칸씩 건너 빼와서 만들어진 수열 다음 지식에서 재미있어 보이는 문제가 있어서 한번 짜 봤다. 문제는 다음과 같다. 2010년 4월 1일 추가 : 여기에 좀 더 재미있는 분석과 코드가 있다. Josephus Problem 이란 이름이 붙은 것 같다. http://k.daum.net/qna/view.html?qid=44T6T 친구가 질문했는데 너무 어려워서 지인들의 설명을 듣고자 질문합니다. 1부터 30까지의 수를 가진 사람이 순서대로 원 주위로 앉아있을 때, 먼저, 9번째 앉아있는 사람을 쫓아내고, 그로부터 9칸을 더 간 18번째 사람을 쫓아낸다. 마찬가지로 9칸을 더 간 27번 사람을 쫓아내고, 그 다음, 또 9칸을 더 간 사람(6번)을 쫓아낸다. 그리 고 나서 9칸을 갈 때에는 9번째 앉았던 쫓겨난 사람은 없는 것으로 치고 9칸 뒤,..
[Euler Project 188] 1777의 1885 거듭거듭제곱의 마지막 8자리 구하기 거듭거듭제곱이란 단어는 tetration의 정확한 한국어 번역어를 몰라서 내가 개발한 번역임. 정확한 정의는 검색하여 보기바람. 매우 재미있음. #!/usr/bin/env python # http://projecteuler.net/index.php?section=problems&id=188 def phi(n0): ''' euler phi function for n, which consists of only 2 and 5 ''' n = n0 pow2 = 0 while n%2 == 0: n/=2 pow2 +=1 n = n0 pow5 = 0 while n%5 == 0: n/=5 pow5 +=1 if pow5 == 0: if pow2 == 0: return 1 else: return 2**(pow2-1) els..
[수학] 페르마 소정리 이해를 위한 장난 rsa를 주제로 한 오일러 프로젝트 문제를 풀다가, 페르마 소정리에 대해서 감이 잘 안 와서 엑셀로 계산을 시켜봤다. p = 3, q = 7 인 상당히 간단한 경우의 계산이다. 엑셀이 상당한 프로그래밍 시간을 줄여주기는 하는데, 내 입맛에 딱 맞춰 결과를 보기에는 아직 익숙하지가 않아서 좀 고달픈 구석이 있다.
[Project Euler 123] (p-1)^n + (p+1)^n % p^2 http://projecteuler.net/index.php?section=problems&id=123 pn 이 n번째 소수 ( 2, 3, 5, 7, 11, ..., )이고, r이 (pn1)n + (pn+1)n 를 pn2으로 나눈 나머지라고 하자. 예를 들어, n = 3, p3 = 5 이고, 43 + 63 = 280 5 mod 25 이다. 이 나머지가 109을 넘는 가장 작은 n은 7037이다. 나머지가 1010을 넘는 가장 작은 n을 구하라. #!/usr/bin/env python # Project Euler Problem 123 def remainder0(p, n): return ((p-1)**n + (p+1)**n)%(p*p) def remainder(p, n): ''' p is a prime. r..
[Project Euler 148] 파스칼 삼각형 mod 7 http://projecteuler.net/index.php?section=problems&id=148 파스칼 삼각형을 7번째 줄까지 써보면, 7로 나누어 떨어지는 것이 없다는 걸 알 수 있다.: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 그러나, 100번째 줄까지를 보면, 5050개의 숫자 중에서 2361개만 7로 나누어 떨어지지 않는다. 10억(109)번째 줄까지 중에서 7로 나누어 떨어지지 않는 것의 갯수를 구하라. 우선, a+b mod n = (a mod n) + (b mod n) mod n 과 같다는 걸 이용해서 그림을 그려보면, 아주 예쁜 프랙탈모양을 이룸을 알 수 있다. 그리고, 숫자를 7진수로 변환한 후 생각하면 훨씬 생각이..