fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(x) x.begin(),x.end()
  4. #define pb push_back
  5. typedef long long ll;
  6. int a[100005];
  7. int sieve[1000005];
  8. vector<int>tree[1000005];
  9. bool visited[1000005];
  10. vector<int>factors[1000005];
  11. void construct(int l,int r,int si)
  12. {
  13.     if(l>r)
  14.         return ;
  15. 	if(l==r)
  16. 	{
  17. 		tree[si]=factors[l];
  18.  
  19. 		return ;
  20. 	}
  21. 	int mid=(l+r)/2;
  22.  
  23. 	construct(l,mid,si*2+1);
  24. 	construct(mid+1,r,si*2+2);
  25.  
  26. 	merge(all(tree[si*2+1]),all(tree[si*2+2]),back_inserter(tree[si]));
  27. 	for(int i=0;i<tree[si].size();i++)
  28. 		  printf("%d ",tree[si][i]);
  29. 		  printf("\n");
  30.  
  31. }
  32. int query(int l,int r,int ql,int qr,int k1,int k2,int si)
  33. {
  34.  
  35. 	if(r<ql||l>qr)
  36. 	{
  37. 	 //   cout<<"si here 1 "<<si<<endl;
  38. 		return 0;
  39. 	}
  40. 	if(l>=ql&&r<=qr)
  41. 	{
  42.         //c//out<<"si here 2 "<<si<<endl;
  43. 		int ans1=lower_bound(tree[si].begin(),tree[si].end(),k1)-tree[si].begin();
  44. 		int ans2=upper_bound(tree[si].begin(),tree[si].end(),k2)-tree[si].begin();
  45. 		return ans2-ans1;
  46. 	}
  47. 	int mid=(l+r)/2;
  48.   //  cout<<"si here 3 "<<si<<endl;
  49. 	return query(l,mid,ql,qr,k1,k2,si*2+1)+query(mid+1,r,ql,qr,k1,k2,si*2+2);
  50.  
  51. }
  52. void prime_factor(int x,int idx)
  53. {
  54. 	while(x!=1)
  55. 	{
  56. 		factors[idx].pb(sieve[x]);
  57. 		x/=sieve[x];
  58. 	}
  59. }
  60. int main()
  61. {
  62. 	int n,q,l,r,x,y;
  63. 	cin>>n;
  64.  
  65. 	for(int i=2;i*i<=1000001;i++)
  66. 	{
  67. 		if(visited[i])
  68. 			continue;
  69. 		for(int j=i*i;j<=1000001;j+=i)
  70. 		{
  71. 			visited[j]=true;
  72. 			sieve[j]=i;
  73. 		}
  74.  
  75. 	}
  76. 	for(int i=2;i<=1000001;i++){
  77. 		if(visited[i]==false)
  78. 		sieve[i]=i;
  79. 	}
  80. 	for(int i=0;i<n;i++)
  81. 	{
  82. 		cin>>a[i];
  83. 		prime_factor(a[i],i);
  84. 	}
  85. 	cin>>q;
  86. 	construct(0,n-1,0);
  87. 	for(int i=0;i<q;i++)
  88. 	{
  89. 		cin>>l>>r>>x>>y;
  90. 		int ans=query(0,n-1,l-1,r-1,x,y,0);
  91. 	//	cout<<ans<<endl;
  92. 	}
  93. 	return 0;
  94. }
  95.  
Success #stdin #stdout 0.03s 67392KB
comments (?)
stdin
copy 
5
2 45 14 546 475
1
2 5 10 1000
stdout
copy 
2 5 3 3 
2 2 5 3 3 7 
13 3 2 7 19 5 5 
2 2 5 3 3 7 13 3 2 7 19 5 5
https://ideone.com/XOqxDU
language:
C++14 (gcc 8.3)
created:
6 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!