15005 - Collatz Conjecture

번역

길이 $N$인 수열 $A$가 주어집니다. $1 \le i \le j \le N$인 $i, j$에 대해서 $f(i,j) = \gcd(a_i, a_{i+1},...,a_j)$를 생각해 봅시다. 모든 $f(i,j)$가 가질 수 있는 값의 개수를 출력하시오.

step 1

$j$가 정해졌고 $i$가 $j$부터 하나씩 감소한다고 생각해 봅시다. 처음에는 $\gcd(a_j)$이니 당연히 $a_j$일 것입니다. 다음은 $\gcd(a_{j-1}, a_j)$, 다음은 $\gcd(a_{j-2}, a_{j-1}, a_j)$가 될 것입니다. 이때, $f(i,j)$는 계속해서 감소하고 $f(i,j)$가 변하는 지점은 많아야 $\log_2 {a_j}$입니다.

step 2

$i$가 $N$부터 1까지 감소하고 각 $i$마다 $j$가 $i$부터 $N$까지 증가한다고 해봅시다. 만약 $f(i, j)=f(i+1, j)$라면 $f(i, j+1)=f(i+1, j+1)$이므로 더 이상 진행하지 않아도 됩니다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<set>
using namespace std;
set<long long int> ss;
long long int ch[500010],b[500010];
long long int gcd(long long int x, long long int y) { return y == 0 ? x : gcd(y, x % y); }
int main() {
	int n, i,j;
	scanf("%d", &n);
	for (i = 1;i <= n;i++) {
		scanf("%lld", &b[i]);
		ch[i] = 0;
	}
	for (i = n;i >= 1;i--) {
		long long int g = b[i];
		ss.insert(g);
		ch[i] = g;
		for (j = i+1;j <= n;j++) {
			g = gcd(g, b[j]);
			if (ch[j] == g) break;
			ch[j] = g;
			ss.insert(g);
		}
	}
	printf("%d", ss.size());
	return 0;
}