흙금이네 블로그

아이디어 학생 수의 공약수와 그 공약수의 개수의 곱의 최댓값을 구한다. 풀이 #1 (Python) 2부터 값을 차례로 증가시키면서 현재 수와 현재 수의 배수가 되는 학생 수 개수 곱의 최댓값을 갱신해 나간다. def solution(): N = int(input()) students = tuple(map(int, input().split())) M = max(students) multiples = [0]*(M+1) for student in students: multiples[student] += 1 res = N for d in range(2, M+1): cnt = sum(multiples[d:M+1:d]) if cnt > 1 and d*cnt > res: res = d*cnt print(res) so..

아이디어 임의의 수 K를 중심으로 양쪽으로 누적된 두 최대공약수의 최대공약수의 최댓값을 구한다. 풀이 #1 (Python) 누적 합 알고리즘과 비슷한 원리로 합이 아닌 최대공약수를 누적해 리스트에 저장해 나간다. import sys input = sys.stdin.readline def solution(): def gcd(a, b): if a > b: a, b = b, a while a: r = b%a b, a = a, r return b N = int(input()) numbers = tuple(map(int, input().split())) gcd_list = [0]*N gcd_list[1] = numbers[0] res = idx = -1 for i in range(1, N-1): gcd_list[..

아이디어 오일러 피 함수로 n과 서로소인 n 이하의 자연수 개수를 구한다. 풀이 #1 (Python) 2 이상의 모든 자연수는 소수의 곱으로 표현할 수 있다. 자연수 \(n\)이 어떤 소수 \(p\)를 소인수로 갖는다면 \(n\) 이하인 \(p\)의 배수는 \(n\)과 서로소가 아니다. \(n\)을 구성하는 소인수 \(p\) 외의 다른 소인수들의 곱을 \(a\)라 할 때, \(n\) 이하인 \(p\)의 배수는 \(\frac{ap^{m}}{p}=ap^{m-1}\)개 존재한다. n과 서로소가 아닌 n 이하의 자연수의 개수를 구하면 조건을 만족하는 k의 개수를 구할 수 있다. 초기값이 n인 결과값을 차례로 이전 소인수들의 배수가 아닌 현재 소인수의 배수의 개수만큼 감소시켜 나간다. 지금 풀이도 어렵긴 하지만 ..