思路

  此题有一个很明显的条件那就是如果一个数组中所有数的lcm在这个数组中，那这个数一定是最大的数，因为lcm一定是大于等于所有数的，所以可以从贪心的角度去考虑，首先如果整个数组的lcm等于最大的数，那么就去删掉这个最大的数，继续观察剩下的数，重复操作，至于为什么可以直接删除最大的数，因为当所有数的lcm等于最大的数时，其他的数一定是最大数的因子，只有删掉最大的数，lcm才会变化，所以删除最大的数一定最优，实现时可以反向操作，那便是从小到大的加数

代码

c++

#include<iostream>
#include<cstring>
#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[2010];
ll lcm(ll a,ll b)
{
    return a*b/__gcd(a,b);
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        int ans=0;
        for(int i=0;i<n;i++)cin>>a[i];
        sort(a,a+n);
        ll cur=1;
        for(int i=0;i<n;i++)
        {
            cur=lcm(cur,a[i]);
            if(cur>1000000000)
            {
                ans=n;
                break;
            }
            if(cur>a[i])
                ans=i+1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static long lcm(long a, long b) {
        return a * b / gcd(a, b);
    }

    static long gcd(long a, long b) {
        while (b != 0) {
            long temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        
        while (T-- > 0) {
            int n = scanner.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
            }
            Arrays.sort(a);
            long cur = 1;
            int ans = 0;

            for (int i = 0; i < n; i++) {
                cur = lcm(cur, a[i]);
                if (cur > 1000000000) {
                    ans = n;
                    break;
                }
                if (cur > a[i]) {
                    ans = i + 1;
                }
            }
            System.out.println(ans);
        }

        scanner.close();
    }
}

python

import math

def lcm(a, b):
    return a * b // math.gcd(a, b)

def main():
    T = int(input())
    
    for _ in range(T):
        n = int(input())
        a = list(map(int, input().split()))
        a.sort()
        cur = 1
        ans = 0

        for i in range(n):
            cur = lcm(cur, a[i])
            if cur > 1000000000:
                ans = n
                break
            if cur > a[i]:
                ans = i + 1
        
        print(ans)

if __name__ == "__main__":
    main()

题目内容

​ 小美有一个长度为n的数组$[a1,a2,...,an]$。他定义一个中所有数的最小公倍数$lcm$不数组$x$是好的,当且仅当数存在于$x$中。例如，数组$[1,2,3,4]$是一个好数组，因为所有元素的$lcm=12$,而$12$不在数组中，所以它是一个好数组;而数组$[2,6,3]$不是好数组，因为所有元素的$lcm=6$,而$6$存在于数组中。 小美希望从$a$中选择一个子序列，使得此子序列是好数组，并且他想知道子序列的最大长度。 如果数组$a$可以通过删除数组$b$中的若干(可能为零或全部)元素得到，则数组$a$是数组$b$的子序列。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≤T≤100)$代表数据组数，每组测试数据描述如下: 第一行输入一个整数$n(1≤n≤2000)$代表数组中的元素数量。 第二行输入n个整数$a1,a2,...,an (1≤a_i≤10^9)$代表数组中的元素。

输出描述

对于每一组测试数据，在一行上输出一个整数，代表可以选择的好子序列的最大长度。

样例1

输入

2
3
1 3 2
5
1 2 3 12 4

输出

3
4

说明

对于第一组测试数据，可以全选。 对于第二组测试数据，选择$[1,2,3,4]$，此时$lcm=12$，不在该子序列中，所以它是好的。