ABC125-C : GCD on Blackboard

작성일

https://atcoder.jp/contests/abc125/tasks/abc125_c

첫번째 접근

  • 2개의 수의 GCD를 찾으려면 그냥 Euclidean Algorithm 쓰면 되는데.. 여러개이고 하나를 바꿀 수 있으므로 각각 다 소인수분해 할듯
  • 일단 학교에서 배운 무식한 방법은 작은 소수부터 나눠나가는거 그러려면 $\sqrt{A}$까지의 소수를 모두 알아야한다.
    • $A = 10^9, sqrt(A) = 3.3 \times 10^4$
    • Euclidean Algorithm 으로 어느정도 할만한듯 하다.
  • 소인수분해 찾기 알고리즘
    • Sieve에 N보다 작은 최소의 소수를 저장하고, 이를 이용해서 찾는 방법: 링크
    • $N \cdot O(\sqrt{A}/2)$: 링크
  • 이번 경우는 $A = 10^9, N = 10^5$ 이므로 최악의 경우는 아래쪽이 더 유리하다.
  • 하지만 계산해보다 보면 결국 모두 $10^9$ 을 넘어간다. 소인수분해쪽은 포기

정해

  • Editorial을 봤는데 GCD가 결합법칙이 성립하는것을 이용하는 방식의 풀이였다. 즉 $g(a,g(b,c)) == g(g(a,b),c)$ 이다.
  • 그것만 생각해내면 Left-Right를 저장해놓은 뒤에 양쪽을 GCD하면 간단하게 풀리는 방식이다. Left, Right 방식은 수족관 풀이법과 동일하다.
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
int gcdImpl(int a, int b) {
	return b ? gcdImpl(b, a % b) : a;
}

int gcd(int a, int b) {
	if (b > a) swap(a,b);
	return gcdImpl(a,b);
}

int gcdOnBlackboard(vector<int>& A) {
	int N = A.size(), ans = 0;
	vector<int> left(N);
	vector<int> right(N);
	
	left[0] = A[0];
	right[N-1] = A[N-1];
	
	for(int i = 1; i < N; i++)
		left[i] = gcd(left[i-1], A[i]);
	for(int i = N-2; i >= 0; i--)
		right[i] = gcd(right[i+1], A[i]);
	
	ans = max(left[N-2], right[1]);
	for(int i = 1; i < N-1; i++)
		ans = max(ans, gcd(left[i-1], right[i+1]));
	
	return ans;
}

https://atcoder.jp/contests/abc125/tasks/abc125_a

  • 2달만에 다시 시작하는 PS.. 기억이 대부분 소실된것 같드아
  • 쉬운 문제부터 가보자해서 A도 풀었는데.. 근데 이건 그냥 너무 쉬운 문제.. 산수문제라서 기록은 패스

https://atcoder.jp/contests/abc125/tasks/abc125_b

  • 그래서 B를 봤는데, B도 어렵지 않아 보임. 그냥 C부터 적어야할듯
  • 주머니가 무한대인 Knapsack 문제인데, 평균값 최대가 아니고 그냥 수액 최대라서 $V_i > C_i$ 인거 집으면 됨
  • 문제를 제대로 안읽어서 WA 맞음 -_-