fork download
copy 
  1. //////////////////  استعن بالله ولا تعجز  //////////////////
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define speed ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  5. #define ll long long int
  6. #define el endl
  7. //======================================================
  8. void File() {
  9. #ifndef ONLINE_JUDGE
  10.     freopen("In.txt", "r", stdin);
  11.     freopen("Out.txt", "w", stdout);
  12. #endif
  13. }
  14. //================================================
  15. int ign=0;
  16. ll merge(ll val,ll res) {
  17.     return __gcd(res,val);
  18. }
  19. //================================================
  20. vector<vector<ll>>spars_table;
  21.  
  22. void SparseTable(const vector<ll>&v) {
  23.     const int n=v.size();
  24.     spars_table.assign(__lg(n)+1,vector<ll>(n));
  25.     for(int i=0;i<n;i++)
  26.         spars_table[0][i]=v[i];
  27.     for (int i = 1; (1<<i) <= n; ++i) {
  28.         for (int j = 0; j+(1<<i) <= n; ++j) {
  29.             spars_table[i][j] = merge(spars_table[i-1][j],spars_table[i-1][j+(1<<i)/2]);
  30.         }
  31.     }
  32. }
  33. //================================================
  34. ll Query(int l, int r) {
  35.     ll len=r-l+1;
  36.     ll res=ign;
  37.     for(int i=0;(1<<i)<=len;i++) {
  38.         if (len>>i&1)
  39.             res=merge(spars_table[i][l],res),l+=(1<<i);
  40.     }
  41.     return res;
  42. }
  43.  
  44. //================================================
  45. void solve() {
  46.     int n; cin>>n;
  47.     vector<ll> v(n);
  48.     for (int i = 0; i < n; i++)
  49.         cin>>v[i];
  50.     SparseTable(v);
  51.     for (auto & i : spars_table) {
  52.         sort(i.rbegin(), i.rend());
  53.     }
  54.     int q; cin>>q;
  55.     while (q--) {
  56.         ll x; cin>>x;
  57.         ll res=0;
  58.         map<ll,ll> mp;
  59.         for (int i =0;i<spars_table.size(); ++i) {
  60.             for (int j = 0; j<spars_table[i].size(); ++j) {
  61.                 if (spars_table[i][j]==x and !mp[pow(2,i)])
  62.                     res+=pow(2,i),mp[pow(2,i)]++;
  63.                 else if (spars_table[i][j]<x)
  64.                     break;            }
  65.         }
  66.         cout<<res<<"\n";
  67.     }
  68.  
  69. }
  70.  
  71. //======================================================
  72. int main()
  73. {
  74.     File();
  75.     speed
  76.     int t=1;
  77.     // cin>>t;
  78.     while(t--) {
  79.         solve();
  80.     }
  81.  
  82. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/bPNHWz
language:
C++ (gcc 8.3)
created:
3 days 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!