原题链接

题解

发现一串数字的lcm一定大于等于这一串数字的最大值，所以如果整个数组的lcm大于 \(a_{max}\) ，直接输出n
否则，注意这里的思维，否则，剩余数字组成的lcm一定小于等于 \(a_{max}\) 且是 \(a_{max}\) 的因子

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[2005];
map<ll,ll> q;
vector<pair<ll,ll> > p;


ll check(ll lcm)
{
    ll tem=1;
    ll cnt=0;
    for(auto [val,num]:p)
    {
        if(lcm%val) continue;

        tem=tem/__gcd(tem,val)*val;
        cnt+=num;
    }
    if(tem==lcm) return cnt;
    return 0;
}
void solve()
{
        ll n;
        cin>>n;
        ll maxs=0;
        for(ll i=1;i<=n;i++)
        {
            cin>>a[i];
            maxs=max(maxs,a[i]);
        }

        ll tem=1;
        for(ll i=1;i<=n;i++)
        {
            tem=tem/__gcd(tem,a[i])*a[i];
            if(tem>maxs)
            {
                cout<<n<<"\n";
                return;
            }
        }



        for(ll i=1;i<=n;i++)  q[a[i]]++;

        for(auto it:q)  p.push_back(it);

        ll ans=0;
        for(ll i=2;i*i<=tem;i++)
        {
            if(tem%i) continue;

            if(!q[i]) ans=max(ans,check(i));
            if(!q[tem/i]) ans=max(ans,check(tem/i));
        }

        cout<<ans<<"\n";

        q.clear();
        p.clear();

}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll t;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}