Submission #2375715

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
using namespace std;

typedef long long ll;

vector<ll> primeFactor(ll x){
  //if(x < 2) return {x}; /*!!!!!!!!!!!!!!!!!!!*/
  assert(x > 1);/*!!!!!!!!!!!!!!!!!!!*/

  vector<ll> res;
  for(ll i=2;i*i <= x;i++)
    while(x%i == 0){
      x/=i;
      res.push_back(i);
    }
  if(x != 1) res.push_back(x);
  return res;
}

int ans[100005], A[100005];

signed main(){
  
  int n, m;
  cin>>n>>m;
  
  map<int,int> cnt;
  
  for(int i=0;i<n;i++){
    
    cin>>A[i];
    
    if( A[i] == 1 ) continue;
    
    set<ll> a;
    
    vector<ll> b = primeFactor(A[i]);
    
    for(auto x : b ) a.insert(x);
    
    vector<ll> c;

    for(auto x : a ) c.push_back(x);
    
    int len = c.size();
    
    for(int j=1;j<(1<<len);j++){
      
      int mul = 1;
      
      for(int k=0;k<len;k++){
	if( j >> k & 1 ) mul *= c[k];
      }
      
      if( __builtin_popcount(j) == 1 ) cnt[mul]++;
      else cnt[mul]--;
      
    }
        
  }
  
  cout<<n<<endl;
  
  for(int i=2;i<=m;i++){
        
    set<ll> a;
    
    vector<ll> b = primeFactor(i);
    
    for(auto x : b ) a.insert(x);
    
    vector<ll> c;

    for(auto x : a ) c.push_back(x);
        
    int len = c.size();
    
    int ans = n;
    
    for(int j=1;j<(1<<len);j++){
      
      int mul = 1;
      
      for(int k=0;k<len;k++){
	if( j >> k & 1 ) mul *= c[k];
      }
      
      ans -= cnt[mul];

    }
    
    cout<<ans<<endl;
    
  }
  
  return 0;
}

Submission Info

Judge Result