fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. vector<ll> spf(1000050);
  6. void computeSPF(){
  7. 	for(ll i=0;i<spf.size();i++)
  8. 		spf[i]=i;
  9. 	for(ll p=2;p<=sqrt(spf.size());p++){
  10. 		if(spf[p]==p){
  11. 			//this is prime
  12. 			for(ll i=p*p;i<=spf.size();i=i+p){
  13. 				if(spf[i]==i)
  14. 					spf[i]=p;
  15. 			}
  16. 		}
  17. 	}
  18. }
  19.  
  20. unordered_map<ll, ll> findPF(ll val){
  21. 	unordered_map<ll, ll> mp1;
  22. 	while(val!=1){
  23. 		ll d = spf[val];
  24. 		mp1[d]++;
  25. 		val=val/d;
  26. 	}
  27. 	return mp1;
  28. }
  29.  
  30. int main() {
  31. 	ll n, m;
  32. 	cin>>n>>m;
  33. 	vector<ll> array(n);
  34. 	unordered_map<ll, ll> mp2;
  35. 	for(ll i=0;i<n;i++)
  36. 		cin>>array[i];
  37. 	computeSPF();
  38. 	ll md = 1e9 + 7;
  39.  
  40. 	//compute PF of M!
  41. 	//M!=1x2x3x...xM so we loop from 2 till M
  42. 	for(ll i=2;i<=m;i++){
  43. 		unordered_map<ll, ll> temp=findPF(i);
  44. 		for(auto it:temp){
  45. 			//Merge in master map m2
  46. 			mp2[it.first] += it.second;
  47. 		}
  48. 		//Now mp2 holds all PF of m!
  49. 	}
  50. 	for(ll i=0;i<array.size();i++){
  51. 		//Store PF of array[i] in mp3
  52. 		unordered_map<ll, ll> mp3=findPF(array[i]);
  53. 		unordered_map<ll, ll> combined=mp2;
  54. 		for(auto it: mp3){
  55. 			combined[it.first]+=it.second;
  56. 		}
  57. 		ll g = 1;
  58. 		for(auto it : combined){
  59. 			g = (g * (it.second + 1)) % md;
  60. 		}
  61. 		cout << g << " ";
  62. 	}
  63. 	cout << "\n";
  64. 	return 0;
  65. }
Success #stdin #stdout 0.01s 11160KB
comments (?)
stdin
copy 
3 3 
1 2 3
stdout
copy 
4 6 6
https://ideone.com/dYL2uj
language:
C++ (gcc 8.3)
created:
2 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!