1. 문제 17427번: 약수의 합 2 (acmicpc.net) 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 2. 풀이 문제를 요약하면 1부터 n까지 각각 약수의 합을 전부 더한 값을 출력하는 문제 시간이 0.5초라서 당연히 1부터 n까지 소인수분해하고 약수의 합을 구한다면 시간초과겠지 약수의 합을 구하는 공식은... https://deepdata.tistory.com/588 약수의 합과 약수의 개수 공식 익히기 1. 약수의 개수 자연수 n의 소인수..
1. 문제 4375번: 1 (acmicpc.net) 4375번: 1 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이1 문제는 n의 배수인, 1로만 이루어진 수 중에서 자리수가 가장 작은 수를 찾는 문제 아주 단순하게는 n보다 큰 1로만 이루어진 수를 생성한 다음에.. 그 수가 n으로 나누어 떨어지는지 검사해보면 된다 n의 길이를 i라 한 다음에... 1로만 이루어진 길이 i인 수부터 시작해서.. n으로 나누어가지고 가장 먼저 나누어 떨어지는 수를 출력 from sys import stdin while 1: try: n = int(stdin.readline()) i = len..
1. 라그랑주의 네 제곱수 정리 모든 자연수 n은 많아야 음이 아닌 4개의 정수의 제곱수 합으로 표현할 수 있다. $$n = a^{2} + b^{2} + c^{2} + d^{2}$$을 만족하는 0 이상의 정수 a,b,c,d가 존재한다. 증명은 매우 까다롭다.. 너무 길어서 따라하기도 힘들다.. https://jjycjnmath.tistory.com/295 [퍼온글] 라그랑주의 네제곱수 정리(Four Square Theorem)와 그 증명 ※ 출처 - http://kevin0960.tistory.com/ 디오판토스의 저서 '산학'에는 '모든 양의 정수는 네 제곱수의 합으로 표현될 수 있다.' 라는 내용이 담겨 있다. 예를 들어, \[ \begin{aligned} 3 &= 1^2 + 1^2 + 1^2 + 0..
1. 문제1 2553번: 마지막 팩토리얼 수 (acmicpc.net) 2553번: 마지막 팩토리얼 수 첫째 줄에 N이 주어진다. N은 20,000보다 작거나 같은 자연수 이다. www.acmicpc.net 2. 풀이 저번에 풀었던 문제와는 다르게 팩토리얼 계산한 값에서 마지막에서 0이 아닌 처음으로 다른 수가 나올때, 그 수를 출력하는 문제 쉽게 생각할 수 있는 방법은..? 저번에 배운 마지막에 0이 나오는 개수를 구하는 방법을 응용하기 마지막에 나오는 0의 개수 k를 구하고, n!을 계산하여 prod라고 저장한 다음에... prod를 $10^{k}$로 나눠준다면? 일의 자리가 정답이 된다 일의 자리는 어떻게 구해? str()로 바꿔서 -1번을 뽑아? 아니 str()로 바꾸는게 생각보다 시간 많이 먹어 ..
1. 문제 1676번: 팩토리얼 0의 개수 (acmicpc.net) 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 풀이 끝에서 0의 개수는 어떻게 세야할까 1000000은 뒤에 0이 6개이기 때문에, $10^{6}$이라고 바로 안다. 이처럼 끝에서 0의 개수가 n개이면, $10^{n}$이라고 바로 알고 있다 다른 수를 예로 들어보면 376129000은 $376129*10^{3}$ 따라서 어떤 수에서 끝의 0의 개수는... 소인수 분해해서 10이 몇개나 있는지 계산하면 될 것이다. 여기서 10은 2와 5의 곱이므로, 소인수분해해서 2와 5의 개수가 몇개나 있는지 계산하면 될 것이다 from..
1. 피사노 주기 피보나치 수열을 자연수 n으로 나눈 나머지가 일정한 주기를 이룬다는 것을 1960년 IBM의 한 직원이 증명했다 예를 들어 0,1로 시작하는 피보나치 수열을 3으로 나눈 나머지는 위와 같이 0,1,1,2,0,2,2,1이 반복된다는 것을 알 수 있다 2. 연습문제 9471번: 피사노 주기 (acmicpc.net) 9471번: 피사노 주기 첫째 줄에 테스트 케이스의 개수 P가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다. www.acmicpc.net 추가로 몇가지 성질이 있다고 제시해주는데 어쨌든 이 문제는 피보나치 수열을 자연수 m으로 나눈 나머지가 주기를 이룬다는 사실을 알고 코딩을 해서 반복되는 수열의 길이를 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
