fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4. const int mod = 1e9+7;
  5. const int MAX_N = 1e6;
  6. unordered_map<ll,ll>factorialPrimeFactors;
  7. vector<ll>spf(MAX_N+1,1);
  8.  
  9.  
  10. void computeSPF(){
  11. 	for(int i=2;i<=MAX_N;i++){
  12. 		spf[i] = i;
  13. 	}
  14.  
  15. 	for(ll i=2;i*i<=MAX_N;i++){
  16. 		if(spf[i]==i){
  17. 			ll start = i*i;
  18. 			for(ll j= start;j<=MAX_N;j+=i){
  19. 				spf[j] = i;
  20. 			}
  21. 		}
  22. 	}
  23. }
  24.  
  25. unordered_map<ll,ll> getPrimeFactorization(ll x){
  26. 	unordered_map<ll,ll>factors;
  27. 	while(x!=1){
  28. 		ll g = spf[x];
  29. 		factors[g]++;
  30. 		x = x/g;
  31. 	}
  32. 	return factors;
  33. }
  34.  
  35. void computeFactorialPrimeFactors(ll M){
  36. 	for(ll i=2;i<=M;i++){
  37. 		unordered_map<ll,ll>factors = getPrimeFactorization(i);
  38. 		for(auto [prime,count]:factors){
  39. 			factorialPrimeFactors[prime] += count;
  40. 		}
  41. 	}
  42. }
  43.  
  44. ll computeDivisors(unordered_map<ll,ll>& factors){
  45. 	ll divisors = 1;
  46. 	for(auto [prime,exp]:factors){
  47. 		divisors = ((divisors * (exp+1)%mod)%mod);
  48. 	}
  49. 	return divisors;
  50. }
  51.  
  52. int main() {
  53. 	ios::sync_with_stdio(false);
  54. 	cin.tie(0);
  55.  
  56. 	ll N,M;
  57. 	cin>>N>>M;
  58. 	computeSPF();
  59. 	vector<ll>A(N);
  60. 	for(ll i=0;i<N;i++){
  61. 		cin>>A[i];
  62. 	}
  63.  
  64. 	computeFactorialPrimeFactors(M);
  65.  
  66. 	vector<ll>B(N);
  67. 	for(ll i=0;i<N;i++){
  68. 		// get factors for A[i]
  69. 		unordered_map<ll,ll>factors = getPrimeFactorization(A[i]);
  70.  
  71. 		// Merge with factorial factors
  72. 		for(auto [prime,exp] : factorialPrimeFactors){
  73. 			factors[prime] += exp;
  74. 		}
  75.  
  76. 		B[i] = computeDivisors(factors);
  77. 	}
  78.  
  79. 	// print divisors
  80. 	for(ll i=0;i<N;i++){
  81. 		cout<<B[i]<<" ";
  82. 	}
  83.  
  84. 	return 0;
  85. }
Success #stdin #stdout 0.02s 11120KB
comments (?)
stdin
copy 
3 3
1 2 3
stdout
copy 
4 6 6
https://ideone.com/KqE96C
language:
C++ (gcc 8.3)
created:
7 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!