fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5.  
  6.  
  7. void computespf(vector<int> &spf){
  8.     ll maxn = 1000000;
  9.     spf.resize(maxn+1);
  10.  
  11.     vector<ll> arr(maxn+1,1);
  12.     for(ll i=0;i<=maxn;i++){
  13.         spf[i]=i;
  14.     }
  15.  
  16.     for(ll i=2;i<=maxn;i++){
  17.         if(arr[i]){
  18.             ll j = i*i;
  19.             while(j<=maxn){
  20.                 if(spf[j]==j){
  21.                     spf[j]=i;
  22.                 }
  23.                 arr[j]=0;
  24.                 j=j+i;
  25.  
  26.  
  27.             }
  28.         }
  29.     }
  30. }
  31.  
  32.  
  33. unordered_map<ll,ll> factorization(ll v1,vector<int> &spf){
  34.     unordered_map<ll,ll> mpp;
  35.     while(v1!=1){
  36.         ll d = spf[v1];
  37.         mpp[d]++;
  38.         v1=v1/d;
  39.     }
  40.     return mpp;
  41.  
  42. }
  43.  
  44. int main() {
  45.      vector<int> spf;
  46.      computespf(spf);
  47.      ll mod = 1e9 + 7;
  48.  
  49.  
  50.      int n,m;
  51.      cin>>n>>m;
  52.  
  53.      unordered_map<ll,ll> mp2;
  54.  
  55.      for(ll i=2;i<=m;i++){
  56.         unordered_map<ll,ll> mpp = factorization(i,spf);
  57.         for(auto it : mpp){
  58.             mp2[it.first] = mp2[it.first] + it.second;
  59.         }
  60.      }
  61.  
  62.      vector<ll> arr(n+1);
  63.  
  64.      for(ll i=1;i<=n;i++){
  65.          cin>>arr[i];
  66.          unordered_map<ll,ll> mp3 = mp2;
  67.          unordered_map<ll,ll> mp1 = factorization(arr[i],spf);
  68.  
  69.          for(auto it : mp1){
  70.             mp3[it.first] = mp3[it.first] + it.second;
  71.          }
  72.          ll g=1;
  73.          for(auto it : mp3){
  74.             g=g%mod*(it.second%mod+1)%mod;
  75.          }
  76.          cout<<g%mod<<" ";
  77.  
  78.      }
  79.  
  80.  
  81.  
  82.  
  83. }
  84.  
Success #stdin #stdout 0.02s 14572KB
comments (?)
stdin
copy 
3 3
1 2 3
stdout
copy 
4 6 6
https://ideone.com/ZkDwcV
language:
C++14 (gcc 8.3)
created:
13 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!