fork download
copy 
  1. // #pragma GCC target ("avx2")
  2. // #pragma GCC optimization ("O3")
  3. // #pragma GCC optimization ("unroll-loops")
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. #define FastRead ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define int long long int
  8. #define ll int
  9. #define cps CLOCKS_PER_SEC
  10. #define bits_count __builtin_popcountll
  11. #define endl '\n'
  12. #define double long double
  13. #define ld double
  14. #define FOR(i,a,n) for (ll i=(a);i<=(n);++i)
  15. #define RFOR(i,a,n) for (ll i=(n);i>=(a);--i)
  16. #define ZERO(a) memset((a),0,sizeof((a)))
  17. #define MINUS(a) memset((a),-1,sizeof((a)))
  18. #define f first
  19. #define s second
  20. #define pb push_back
  21. #define mk make_pair
  22. #define all(g) g.begin(),g.end()
  23. #define sz(x) (ll)x.size()
  24. #define pr pair<int,int>
  25. #define MOD 1000000007
  26. int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }
  27. int fastMin(int x, int y) { return (((y-x)>>(32-1))&(x^y))^x; }
  28. int power(int x,int y){ int res = 1; while(y>0){   if(y&1) res = (res*x)%MOD;
  29.         y >>= 1; x = (x*x)%MOD; } return res; }
  30.  
  31. // #include <ext/pb_ds/assoc_container.hpp> // Common file
  32. // #include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_updat
  33. // using namespace __gnu_pbds;
  34. // typedef tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  35. // const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
  36. // struct chash { int operator()(int x) const { return x ^ RANDOM; }};
  37. // cc_hash_table<int, int, hash<int>> cnt;
  38.  
  39. const int MAXN = 1e5 + 10;
  40. int M[MAXN],phi[MAXN];
  41. int is_composite[MAXN];
  42. vector<int> prime;
  43.  
  44. void linear_seive_with_mobius_and_phi(){
  45.     M[1] = 1,phi[1] = 1;
  46.  
  47.     for(int i=2;i<MAXN;i++){
  48.         if(!is_composite[i]){
  49.             prime.push_back(i);
  50.             M[i] = -1,phi[i] = i-1;
  51.         }
  52.         for(int j=0;j<prime.size() && i*prime[j] < MAXN;j++){
  53.             is_composite[i*prime[j]] = true;
  54.             if(i%prime[j] == 0){
  55.                 M[i*prime[j]] = 0;
  56.                 phi[i*prime[j]] = phi[i]*prime[j];
  57.                 break;
  58.             }else {
  59.                 M[i*prime[j]] = M[i]*M[prime[j]];
  60.                 phi[i*prime[j]] = phi[i]*phi[prime[j]];
  61.             }
  62.         }
  63.     }
  64. }
  65.  
  66. int a[MAXN];
  67. int freq[MAXN];
  68. int sum[MAXN];
  69. int ans[MAXN];
  70.  
  71. void solve(){
  72.     int n,q; cin>>n>>q;
  73.     FOR(i,1,n){
  74.         cin>>a[i]; freq[a[i]]++;
  75.     }    
  76.  
  77.     FOR(i,1,MAXN-1){
  78.         for(int j=i;j<MAXN;j+=i){
  79.             sum[i] += freq[j];
  80.         }
  81.     }
  82.  
  83.     for(int g=1;g<MAXN;g++){
  84.         for(int l=g;l<MAXN;l+=g){
  85.             ans[g] += sum[l]*sum[l]*M[l/g];
  86.         }
  87.         ans[g] += freq[g];
  88.         ans[g] /= 2;
  89.     }
  90.  
  91.     while(q--){
  92.         int k; cin>>k;
  93.         cout<<ans[k]<<endl;
  94.     }
  95. }
  96.  
  97. signed main(){
  98.  
  99.     FastRead; 
  100.  
  101.     linear_seive_with_mobius_and_phi();
  102.     int t = 1; 
  103.     // cin>>t;
  104.     FOR(i,1,t){
  105.         // cout<<"Case #"<<i<<": ";
  106.         solve();
  107.     }
  108. }
  109.  
  110.  
Success #stdin #stdout 0.02s 7732KB
comments (?)
stdin
copy 
5 3
1 2 3 4 6
1
2
3
stdout
copy 
7
4
2
https://ideone.com/32tjY8
language:
C++14 (gcc 8.3)
created:
4 years 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!