2 solutions

  • 0
    @ 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;
    }
    
    //███████████████████████████████████████████████████████████████████████████████████████████████████████
    //█░░░░░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░███░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░░░█
    //█░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░░░░░░░░░██░░▄▀░░█░░▄▀▄▀▄▀▄▀░░░░█░░▄▀▄▀▄▀░░█░░▄▀░░░░░░░░░░██░░▄▀░░█░░▄▀▄▀▄▀▄▀▄▀░░█
    //█░░▄▀░░░░░░░░░░█░░▄▀▄▀▄▀▄▀▄▀░░██░░▄▀░░█░░▄▀░░░░▄▀▄▀░░█░░░░▄▀░░░░█░░▄▀▄▀▄▀▄▀▄▀░░██░░▄▀░░█░░▄▀░░░░░░░░░░█
    //█░░▄▀░░█████████░░▄▀░░░░░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░░░░░▄▀░░██░░▄▀░░█░░▄▀░░█████████
    //█░░▄▀░░░░░░░░░░█░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░█████████
    //█░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░░░░░█
    //█░░▄▀░░░░░░░░░░█░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░██░░▄▀░░█░░▄▀░░██░░▄▀░░█
    //█░░▄▀░░█████████░░▄▀░░██░░▄▀░░░░░░▄▀░░█░░▄▀░░██░░▄▀░░███░░▄▀░░███░░▄▀░░██░░▄▀░░░░░░▄▀░░█░░▄▀░░██░░▄▀░░█
    //█░░▄▀░░░░░░░░░░█░░▄▀░░██░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░░░▄▀▄▀░░█░░░░▄▀░░░░█░░▄▀░░██░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░░░░░▄▀░░█
    //█░░▄▀▄▀▄▀▄▀▄▀░░█░░▄▀░░██░░░░░░░░░░▄▀░░█░░▄▀▄▀▄▀▄▀░░░░█░░▄▀▄▀▄▀░░█░░▄▀░░██░░░░░░░░░░▄▀░░█░░▄▀▄▀▄▀▄▀▄▀░░█
    //█░░░░░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░███░░░░░░░░░░█░░░░░░██████████░░░░░░█░░░░░░░░░░░░░░█
    //███████████████████████████████████████████████████████████████████████████████████████████████████████
    
    
  • 0
    @ 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
9
Category
Number_Theory Click to Show
Tags
# Submissions
106
Accepted
6
Accepted Ratio
6%
Uploaded By