# G. Farmer John's Last Wish [문제 링크](https://codeforces.com/contest/2148/problem/G) ## Problem Statement Bessie has found an array $a$ of length $n$ on the floor. There appears to be a handwritten note lying next to the array, seemingly written by Farmer John. The note reads: Help me, dear Bessie! Let $f(a)$ denote the maximum integer $k$ in the range $[1,n)$ such that $\gcd(a_1, a_2, \ldots, a_k) > \gcd(a_1, a_2, \ldots, a_{k+1})$, or $0$ if no such $k$ exists. Bessie decides to help FJ. She defines $g(a)$ to represent the maximum value of $f(a)$ over all possible reorderings of $a$. Bessie decides to not only find $g(a)$, but also the value of $g(p)$ for all prefixes $p$ of $a$. Output $n$ integers, the $i$'th of which is $g([a_1, a_2, \ldots, a_i])$. ## Input The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The first line of each test case contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$). The following line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$). It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. ## Output For each test case, output $n$ integers on a new line: the $i$'th of which should be $g([a_1, a_2, \ldots, a_i])$. ## 풀이 입력되는 수의 약수를 전부 등장 횟수 1씩 증가시키고, 현재 수까지의 최대공약수보다 큰 수들의 최대 등장횟수를 세주면 된다. ``` c++ #include<bits/stdc++.h> using namespace std; int cnt[200'001]; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--) { int n; cin >> n; int gcdVal, maxCnt=0, maxFind=n; memset(cnt, 0, sizeof cnt); for(int i=0;i<n;i++) { int a; cin >> a; gcdVal = i==0 ? a : gcd(gcdVal, a); for(int j=1;j*j<=a;j++) { if(a%j==0) { cnt[j]++; if(j!=a/j) cnt[a/j]++; if(j>gcdVal) maxCnt = max(maxCnt, cnt[j]); if(a/j>gcdVal) maxCnt = max(maxCnt, cnt[a/j]); } } while(maxFind>gcdVal) maxCnt = max(maxCnt, cnt[maxFind--]); cout << min(maxCnt, i) << ' '; } cout << '\n'; } } ```