2 solutions
-
0tin.le LV 4 @ 2024-10-04 21:24:37
//████████╗██╗███╗░░██╗ ██╗░░░░░███████╗ //╚══██╔══╝██║████╗░██║ ██║░░░░░██╔════╝ //░░░██║░░░██║██╔██╗██║ ██║░░░░░█████╗░░ //░░░██║░░░██║██║╚████║ ██║░░░░░██╔══╝░░ //░░░██║░░░██║██║░╚███║ ███████╗███████╗ //░░░╚═╝░░░╚═╝╚═╝░░╚══╝ ╚══════╝╚══════╝ // __________________ // | ________________ | // || ____ || // || /\ | || // || /__\ | || // || / \ |____ || // ||________________|| // |__________________| // \###################\ // \###################\ // \ ____ \ // \_______\___\_______\ // An AC a day keeps the doctor away. #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define vt vector #define all(x) begin(x), end(x) #define allr(x) rbegin(x), rend(x) #define ub upper_bound #define lb lower_bound #define db double #define ld long db #define ll int64_t #define vll vt<ll> #define vvll vt<vll> #define pll pair<ll, ll> #define vpll vt<pll> #define vc vt<char> #define vvc vt<vc> #define vi vt<int> #define vvi vt<vi> #define vvvi vt<vvi> #define pii pair<int, int> #define vpii vt<pii> #define vs vt<string> #define vvs vt<vs> #define vb vt<bool> #define vvb vt<vb> #define vvpii vt<vpii> #define vd vt<db> #define ar(x) array<int, x> #define var(x) vt<ar(x)> #define pq priority_queue #define mset(m, v) memset(m, v, sizeof(m)) #define pb push_back #define ff first #define ss second #define sv string_view #define MP make_pair #define MT make_tuple #define rsz resize #define sum(x) accumulate(all(x), 0LL) #define srt(x) sort(all(x)) #define srtR(x) sort(allr(x)) #define srtU(x) sort(all(x)), (x).erase(unique(all(x)), (x).end()) #define SORTED(x) is_sorted(all(x)) #define rev(x) reverse(all(x)) #define gcd(a, b) __gcd(a, b) #define lcm(a, b) (a * b) / gcd(a, b) #define MAX(a) *max_element(all(a)) #define MIN(a) *min_element(all(a)) //SGT DEFINE #define lc i * 2 + 1 #define rc i * 2 + 2 #define lp lc, left, middle #define rp rc, middle + 1, right #define entireTree 0, 0, n - 1 #define midPoint left + (right - left) / 2 #define pushDown push(i, left, right) #define iterator int i, int left, int right #define IOS ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0) struct custom { static const uint64_t C = 0x9e3779b97f4a7c15; const uint32_t RANDOM = std::chrono::steady_clock::now().time_since_epoch().count(); size_t operator()(uint64_t x) const { return __builtin_bswap64((x ^ RANDOM) * C); } size_t operator()(const std::string& s) const { size_t hash = std::hash<std::string>{}(s); return hash ^ RANDOM; } }; template <class K, class V> using umap = std::unordered_map<K, V, custom>; template <class K> using uset = std::unordered_set<K, custom>; template<typename T1, typename T2> std::ostream& operator<<(std::ostream& o, const std::pair<T1, T2>& p) { return o << "{" << p.ff << " , " << p.ss << "}"; } auto operator<<(auto &o, const auto &x) -> decltype(end(x), o) { o << "{"; int i = 0; for (const auto &e : x) { if (i++) o << " , "; o << e; } return o << "}"; } template <typename T1, typename T2> istream &operator>>(istream& in, pair<T1, T2>& input) { return in >> input.ff >> input.ss; } template <typename T> istream &operator>>(istream &in, vector<T> &v) { for (auto &el : v) in >> el; return in; } template<typename K, typename V> auto operator<<(std::ostream &o, const std::map<K, V> &m) -> std::ostream& { o << "{"; int i = 0; for (const auto &[key, value] : m) { if (i++) o << " , "; o << key << " : " << value; } return o << "}"; } template<typename T> vt<T> uniqued(vt<T> arr) { srtU(arr); return arr; } #ifdef LOCAL #define debug(x...) debug_out(#x, x) void debug_out(const char* names) { std::cerr << std::endl; } template <typename T, typename... Args> void debug_out(const char* names, T value, Args... args) { const char* comma = strchr(names, ','); std::cerr << "[" << (comma ? std::string(names, comma) : names) << " = " << value << "]"; if (sizeof...(args)) { std::cerr << ", "; debug_out(comma + 1, args...); } else { std::cerr << std::endl; } } #define startClock clock_t tStart = clock(); #define endClock std::cout << std::fixed << std::setprecision(10) << "\nTime Taken: " << (double)(clock() - tStart) / CLOCKS_PER_SEC << " seconds" << std::endl; #else #define debug(...) #define startClock #define endClock #endif mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define eps 1e-9 #define M_PI 3.14159265358979323846 const static ll INF = 1LL << 60; const static int inf = 1e9 + 33; const static int MK = 20; const static int MX = 2e6 + 5; const static int MOD = 1e9 + 7; int pct(int x) { return __builtin_popcountll(x); } const vvi dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}}; // UP, DOWN, LEFT, RIGHT int modExpo(ll base, ll exp, ll mod) { ll res = 1; base %= mod; while(exp) { if(exp & 1) res = (res * base) % mod; base = (base * base) % mod; exp >>= 1; } return res; } void solve() { int n; cin >> n; vi a(n); cin >> a; srtR(a); int m = MAX(a) + 1; vi freq(m); for(auto& it : a) freq[it]++; vi divisor; int M = (n + 1) / 2; vvi arr(m); for(int i = 2; i < m; i++) { int cnt = 0; for(int j = i; j < m; j += i) { arr[j].pb(i); cnt += freq[j]; } if(cnt >= n - M) divisor.pb(i); } if(divisor.empty()) { cout << 2 << endl; return; } for(int i = 0; i < m; i++) rev(arr[i]); int res = 0; for(auto& x : divisor) { vi A; int c = 0, g = 0; for(auto& it : a) { if(it % x) g = gcd(g, it), c++; else A.pb(it); } int ans = 1; int target = A.size() >= M ? n - M : M; for(auto& j : arr[g]) { int extra = 0, ok = 0; for(auto& it : A) { if(it % j == 0) extra++; if(extra + c >= target) { ok = true; ans = j; break; } } if(ok) break; } res = max(res, x + ans); } cout << res << endl; } signed main() { IOS; startClock //generatePrime(); int t = 1; cin >> t; for(int i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; solve(); } //endClock return 0; } //███████████████████████████████████████████████████████████████████████████████████████████████████████ //█░░░░░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░███░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░░░█ //█░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░░░░░░░░░██░░▄▀░░█░░▄▀▄▀▄▀▄▀░░░░█░░▄▀▄▀▄▀░░█░░▄▀░░░░░░░░░░██░░▄▀░░█░░▄▀▄▀▄▀▄▀▄▀░░█ //█░░▄▀░░░░░░░░░░█░░▄▀▄▀▄▀▄▀▄▀░░██░░▄▀░░█░░▄▀░░░░▄▀▄▀░░█░░░░▄▀░░░░█░░▄▀▄▀▄▀▄▀▄▀░░██░░▄▀░░█░░▄▀░░░░░░░░░░█ //█░░▄▀░░█████████░░▄▀░░░░░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░░░░░▄▀░░██░░▄▀░░█░░▄▀░░█████████ //█░░▄▀░░░░░░░░░░█░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░█████████ //█░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░░░░░█ //█░░▄▀░░░░░░░░░░█░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░█ //█░░▄▀░░█████████░░▄▀░░██░░▄▀░░░░░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░░░░░▄▀░░█░░▄▀░░██░░▄▀░░█ //█░░▄▀░░░░░░░░░░█░░▄▀░░██░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░░░▄▀▄▀░░█░░░░▄▀░░░░█░░▄▀░░██░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░░░░░▄▀░░█ //█░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░██░░░░░░░░░░▄▀░░█░░▄▀▄▀▄▀▄▀░░░░█░░▄▀▄▀▄▀░░█░░▄▀░░██░░░░░░░░░░▄▀░░█░░▄▀▄▀▄▀▄▀▄▀░░█ //█░░░░░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░███░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░░░█ //███████████████████████████████████████████████████████████████████████████████████████████████████████
-
02024-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
- 9
- Category
- Number_Theory Click to Show
- Tags
- # Submissions
- 106
- Accepted
- 6
- Accepted Ratio
- 6%
- Uploaded By