fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6.  
  7.  
  8. const int M = 1000000007;
  9. const int N = 3e5+9;
  10. const int INF = 2e9+1;
  11. const int LINF = 2000000000000000001;
  12.  
  13. inline int power(int a, int b, int mod=M) {
  14.     int x = 1;
  15.     a %= mod;
  16.     while (b) {
  17.         if (b & 1) x = (x * a) % mod; 
  18.         a = (a * a) % mod;
  19.         b >>= 1;
  20.     }
  21.     return x;
  22. }
  23.  
  24.  
  25.  
  26.  
  27. //_ ***************************** START Below *******************************
  28.  
  29.  
  30.  
  31.  
  32. vector<int> a;
  33.  
  34. int bruteforce(int n){
  35.  
  36.     unordered_map<int,int> mp;
  37.     for(int i=0; i<n; i++){
  38.         mp[a[i]]++;
  39.     }
  40.  
  41.     int maxi = 0;
  42.     for(int i=1; i<=n; i++){
  43.         int ct = 0;
  44.  
  45.         ct += mp[i];
  46.         if(i!=1) ct += mp[1];
  47.  
  48.  
  49.         for(int j=2; j*j<=i; j++){
  50.             if(i%j != 0) continue;
  51.  
  52.             ct += mp[j];
  53.  
  54.             if(j != i/j){
  55.                 ct += mp[i/j];
  56.             }
  57.         }
  58.         maxi = max(maxi, ct);
  59.     }
  60.  
  61.     return maxi;
  62. }
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69. int consistency(int n){
  70.  
  71.     vector<int> freq(n+1, 0);
  72.     vector<int> seive(n+1, 0);
  73.  
  74.     for(int i=0; i<n; i++){
  75.         if(a[i] > n) continue;
  76.         freq[a[i]]++;
  77.     }
  78.  
  79.  
  80.     for(int i=1; i<=n; i++){
  81.         if(freq[i] == 0) continue;
  82.  
  83.         for(int j=1*i; j<=n; j+=i){
  84.             seive[j] += freq[i];
  85.         }
  86.     }
  87.  
  88.     int maxi = 0;
  89.     for(int i=1; i<=n; i++){
  90.         maxi = max(maxi, seive[i]);
  91.     }
  92.  
  93.     return maxi;
  94. }
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105. int practice(int n){
  106.  
  107.  
  108.     return 0;
  109. }
  110.  
  111.  
  112.  
  113.  
  114.  
  115. void solve() {
  116.  
  117.  
  118.     int n;
  119.     cin>> n;
  120.  
  121.     a.resize(n);
  122.     for(int i=0; i<n; i++) cin >> a[i];
  123.  
  124.     cout << consistency(n) << endl;
  125.  
  126.  
  127. }
  128.  
  129.  
  130.  
  131.  
  132.  
  133. int32_t main() {
  134.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  135.  
  136.     int t = 1;
  137.     cin >> t;
  138.     while (t--) {
  139.         solve();
  140.     }
  141.  
  142.     return 0;
  143. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
7
5
1 2 3 4 5
3
2 2 2
6
3 1 3 4 9 10
9
1 3 2 4 2 3 7 8 5
1
10
8
7 11 6 8 12 4 4 8
10
9 11 9 12 1 7 2 5 8 10
stdout
copy 
3
3
3
5
0
4
4
https://ideone.com/H0LAd6
language:
C++14 (gcc 8.3)
created:
15 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!