赛时看到这个范围以为是dp 结果寄了

数论:
先对a升序排序，然后特判答案是否为a[n] 
即判断++lcm[a[1] to a[n]] != a[n]++ 是否成立
如果成立则答案就是n
否则 lcm[a[1] to a[n]] 的子序列的lcm 就是n的某个因子

例子：2 3 6 12
于是枚举a[n]的因子d是否满足条件：
1.没有在原数列中出现
2.存在一个子序列满足lcm = d, 就是数列中d的因子是否满足lcm = d

tips:
1.如果用求a 1 to n-1的lcm是否等于an的话 ++可能会爆longlong++
所以直接用an对a 1to n-1 取模（除法）看是否是lcm
2.用map标注此因子是否在an中出现
3.只有当最终的lcm == r时候才能 对最大值做判断。

时间复杂度O(t(sqrt(an) + n*1e3)) 约等于 2e6

code:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2020;
ll a[N];
int t;
set<int>elem;

ll gcd(ll a, ll b){
    return b? gcd(b, a % b) : a;
}

ll get_lcm(ll a, ll b){
    return a * b / gcd(a, b);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> t;
    while(t--){
        int n;
        cin >> n;
        map<int, int>h;
        for(int i = 1;i <= n;i++){
            cin >> a[i];
            h[a[i]] = 1;
        }
        sort(a + 1, a + 1 + n);

        bool flag = 1;
        for(int i = 1;i <= n;i++){
            if(a[n] % a[i]){
                flag = false;
                break;
            }
        }
        if(!flag){
            cout << n << endl;
            continue;
        }

            for(int i = 2;i <= sqrt(a[n]);i++){
                if(a[n] % i == 0){
                    elem.insert(i);
                    elem.insert(a[n] / i);
                }
            }

            ll mx = 0;
            while(elem.size()){
                int r = *elem.begin();
                if(h[r]){
                    elem.erase(r);
                    continue;
                }

                ll cnt = 0, lcm = 1;
                for(int i = 1;i <= n - 1;i++){
                    if(r < a[i])break;

                    if(r % a[i] == 0){
                        cnt++;
                        lcm = get_lcm(lcm, a[i]);
                    }
                    if(lcm == r)mx = max(cnt, mx);
                }
                elem.erase(r);
            }
            cout << mx << endl;
    }   
    return 0;
}