Cute Rabbit

Python3 解法, 执行用时: 335ms, 内存消耗: 16440K, 提交时间: 2022-10-24 23:16:47

from math import *
n = int(input())

ls = list(map(int,input().split()))

ls.sort()

t = ls.count(ls[0])

ans = n - t

g = [0 for i in range(n + 10)]
l = [0] + ls[:] + [0]

g[n] = ls[-1] - ls[-2]

for i in range(1, n):
    g[i] = ls[i] - ls[i - 1]

for i in range(n, 0, -1):
    g[i] = gcd(g[i], g[i + 1])
    
l[0] = 1

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

for i in range(1, n - 1):
    l[i] = lcm(l[i - 1], l[i])
    if l[i] > 1e9:
        break;
    if g[i + 1] % l[i] == 0:
        ans = max(ans, i)

flag = True

for num in ls:
    if ls[-1] % num != 0:
        flag = False
        break

if flag:
    ans = n - 1

print(ans)

C++(g++ 7.5.0) 解法, 执行用时: 38ms, 内存消耗: 1432K, 提交时间: 2023-04-05 17:43:31

#include <bits/stdc++.h>
using namespace std;

int main(){
  int n; cin>>n;
  vector<int> a(n+1);
  for(int i = 1;i <= n; i++)
    cin>>a[i];
  sort(a.begin()+1,a.end());
  int mod = a[n]%a[1];
  int cnt1 = 0,cnt2 = 0;
  int ans = 0;
  bool f = 1;
  for(int i = 1;i <= n; i++){
    if(a[i] == a[1])
      cnt1++;
    else
      break;
  }
  ans = n-cnt1;
  f = 1;
  for(int i = 1;i < n; i++){
    if(a[n]%a[i] != mod)
      break;
    else
      cnt2 = i;
  }
  ans = max(ans,cnt2);
  cout<<ans<<endl;
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 21ms, 内存消耗: 816K, 提交时间: 2023-05-13 15:17:05

#include <bits/stdc++.h>
using namespace std;
const int N=101000;

int a[N],n,cnt1,cnt2;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        if(a[i]==a[1]) cnt1++;
    for(int i=1;i<n;i++)
        if(a[n]%a[i]!=a[n]%a[1]) break;
        else cnt2=i;
    cout<<max(n-cnt1,cnt2)<<'\n';
    return 0;
}

详情