1 solutions
-
0Bullet LV 4 @ 2024-08-25 13:17:45
Code (C++) :
#include<bits/stdc++.h> using namespace std; const long long M=3e5+10,MOD=1000000000; typedef long long ll; int arr[M]; int limit=100000; int fre[M]; int c[2]; int n; vector<int>finddivisor(int x){ vector<int>d; for(int i=1;i*i<=x;i++){ if(x%i==0){ d.push_back(i); if(x/i==i)continue; d.push_back(x/i); } } return d; } int solve(vector<int>a,int target){ int mx=0; for(auto i:a){ int cnt=0; vector<int>f(limit+1,0); for(int j=i;j<=limit;j+=i){ f[j]=fre[j]; cnt+=f[j]; } if(cnt<target)continue; if(cnt==n){ mx=max(mx,i+c[0]); continue; } int num=0; for(int j=1;j<=limit;j++){ if(fre[j]!=f[j]){ num=j; break; } } vector<int>d=finddivisor(num); int rem=n-target; for(auto j:d){ int even_pos=0; int common=0; for(int div=j;div<=limit;div+=j){ if(f[div]){ common+=f[div]; } else if(fre[div])even_pos+=fre[div]; } int odd_pos=cnt-common; if(odd_pos+even_pos+common!=n)continue; if(odd_pos+common>=target && even_pos+common>=rem){ mx=max(mx,i+j); } } } return mx; } vector<int>finddiv(int x){ vector<int>d; for(int i=1;i*i<=x;i++){ if(x%i==0){ d.push_back(i); if(x/i==i)continue; d.push_back(x/i); } } return d; } int main() { ios::sync_with_stdio(false); cin.tie(0); int t=1; cin>>t; while(t--){ cin>>n; for(int i=1;i<=n;i++)cin>>arr[i-1],fre[arr[i-1]]++; sort(arr,arr+n); vector<int>a=finddiv(arr[0]); c[0]=c[1]=1; for(int i=1;i<=limit;i++){ int odd=(n+1)/2; int even=n/2; int cnt=0; for(int j=i;j<=limit;j+=i){ cnt+=fre[j]; } if(cnt>=odd)c[1]=i; if(cnt>=even)c[0]=i; } cout<<max(solve(a,n/2),solve(a,(n+1)/2))<<"\n"; for(int i=1;i<=limit;i++)fre[i]=0; } return 0; }
- 1
Information
- ID
- 1077
- Difficulty
- 8
- Category
- Number_Theory Click to Show
- Tags
- # Submissions
- 72
- Accepted
- 6
- Accepted Ratio
- 8%
- Uploaded By