fork download
copy 
  1. /**
  2. *
  3. * Author: MARS
  4. * Lang: GNU C++14
  5. *
  6. **/
  7.  
  8. #include<bits/stdc++.h>
  9. using namespace std;
  10.  
  11. typedef long long ll;
  12.  
  13. const int N=1000010;
  14. unordered_map<ll,int>frq;
  15. vector<pair<ll,int>>pr;
  16. int ans=0;
  17.  
  18. void f(int i, ll x){
  19.     if(i == pr.size()){
  20.         ans+=frq[x];
  21.         return ;
  22.     }
  23.  
  24.     int p=pr[i].second;
  25.     ll y=1;
  26.  
  27.     for(int j=0 ; j<=p ; j++){
  28.         f(i+1, x*y);
  29.         y*=pr[i].first;
  30.     }
  31. }
  32.  
  33. int main(){
  34.     int n;
  35.     scanf("%d",&n);
  36.     for(int i=0 ; i<n ; i++){
  37.         ll x;
  38.         scanf("%lld",&x);
  39.         frq[x]++;
  40.     }
  41.  
  42.     int q;
  43.     scanf("%d",&q);
  44.     for(int qn=1 ; qn<=q ; qn++){
  45.         ll k;
  46.         scanf("%lld",&k);
  47.         pr.clear();
  48.         for(ll i=2 ; i*i*i<=k ; i++){
  49.             int cnt=0;
  50.             while(k%i == 0){
  51.                 cnt++;
  52.                 k/=i;
  53.             }
  54.             if(cnt)
  55.                 pr.push_back({i, cnt});
  56.         }
  57.  
  58.         if(k > 1)
  59.             pr.push_back({sqrt(k), 2});
  60.  
  61.         ans=0;
  62.         f(0,1);
  63.         printf("Query %d: %d\n",qn,ans);
  64.     }
  65.  
  66. }
  67.  
Success #stdin #stdout 0s 4428KB
comments (?)
stdin
copy 
6
1 8 4 18 13 8
4
16
36
8
169
stdout
copy 
Query 1: 4
Query 2: 3
Query 3: 4
Query 4: 2
https://ideone.com/UfzFmE
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!