fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define MOD 1000000007
  5. #define N 400001
  6. vector<int>primes;
  7. int pos[301];
  8. vector<int>v[301];
  9. struct node
  10. {
  11. 	ll mask=0;
  12. 	ll p=1;
  13. }t[4*N+1],lazy[4*N+1];
  14. int a[N+1];
  15. ll pwr(ll a,ll b)
  16. {
  17. 	ll k=1;
  18. 	while(b)
  19. 	{
  20. 		if(b&1)
  21. 			k*=a;
  22. 		a*=a;
  23. 		k%=MOD;
  24. 		a%=MOD;
  25. 		b/=2;
  26. 	}
  27. 	return k;
  28. }
  29. void sieve()
  30. {
  31. 	for(int i=2;i<=300;++i)
  32. 	{
  33. 		if(!v[i].empty())
  34. 			continue;
  35. 		pos[i]=primes.size();
  36. 		primes.push_back(i);
  37. 		for(int j=i;j<=300;j+=i)
  38. 			v[j].push_back(i);
  39. 	}
  40. }
  41. void init(int nd,int s,int e)
  42. {
  43. 	lazy[nd].p=1;
  44. 	lazy[nd].mask=0;
  45. 	if(s==e)
  46. 	{
  47. 		t[nd].p=a[s];
  48. 		for(int i=0;i<v[a[s]].size();++i)
  49. 			t[nd].mask|=(1 <<pos[v[a[s]][i]]);
  50. 	}
  51. 	else
  52. 	{
  53. 		int m=s+(e-s)/2;
  54. 		init(2*nd,s,m);
  55. 		init(2*nd+1,m+1,e);
  56. 		t[nd].mask=(t[2*nd].mask|t[2*nd+1].mask);
  57. 		t[nd].p=(t[2*nd].p*t[2*nd+1].p)%MOD;
  58. 	}
  59. }
  60. void upd(ll nd,ll s,ll e,ll l,ll r,ll val)
  61. {
  62. 	if(lazy[nd].p!=1)
  63. 	{
  64. 		t[nd].p=(t[nd].p*pwr(lazy[nd].p,e-s+1))%MOD;
  65. 		t[nd].mask=(t[nd].mask|lazy[nd].mask);
  66. 		if(s!=e)
  67. 		{
  68. 			lazy[2*nd].p=(lazy[2*nd].p*lazy[nd].p)%MOD;
  69. 			lazy[2*nd+1].p=(lazy[2*nd+1].p*lazy[nd].p)%MOD;
  70. 			lazy[2*nd].mask=(lazy[2*nd].mask|lazy[nd].mask);
  71. 			lazy[2*nd+1].mask=(lazy[2*nd+1].mask|lazy[nd].mask);
  72. 		}
  73. 		lazy[nd].mask=0;
  74. 		lazy[nd].p=1;
  75. 	}
  76. 	if(s>r||e<l||s>e)
  77. 		return ;
  78. 	if(s>=l&&e<=r)
  79. 	{
  80. 		t[nd].p=(t[nd].p*pwr(val,e-s+1))%MOD;
  81. 		for(int i=0;i<v[val].size();++i)
  82. 		{
  83. 			t[nd].mask|=(1<<(pos[v[val][i]]));
  84. 			if(s!=e)
  85. 			{
  86. 				lazy[2*nd].mask|=(1 <<(pos[v[val][i]]));
  87. 				lazy[2*nd+1].mask|=(1 <<(pos[v[val][i]]));
  88. 			}
  89. 		}
  90. 		if(s!=e)
  91. 		{
  92. 			lazy[2*nd].p=(lazy[2*nd].p*val)%MOD;
  93. 			lazy[2*nd+1].p=(lazy[2*nd+1].p*val)%MOD;
  94. 		}
  95. 		return;
  96. 	}
  97. 	int m=s+(e-s)/2;
  98. 	upd(2*nd,s,m,l,r,val);
  99. 	upd(2*nd+1,m+1,e,l,r,val);
  100. 	t[nd].mask=t[2*nd].mask|t[2*nd+1].mask;
  101. 	t[nd].p=(t[2*nd].p*t[2*nd+1].p)%MOD;
  102. }
  103. pair<ll,ll> q(int nd,int s,int e,int l,int r)
  104. {
  105. 	if(lazy[nd].p!=1)
  106. 	{
  107. 		t[nd].p=(t[nd].p*pwr(lazy[nd].p,e-s+1))%MOD;
  108. 		t[nd].mask=(t[nd].mask|lazy[nd].mask);
  109. 		if(s!=e)
  110. 		{
  111. 			lazy[2*nd].p=(lazy[2*nd].p*lazy[nd].p)%MOD;
  112. 			lazy[2*nd+1].p=(lazy[2*nd+1].p*lazy[nd].p)%MOD;
  113. 			lazy[2*nd].mask=(lazy[2*nd].mask|lazy[nd].mask);
  114. 			lazy[2*nd+1].mask=(lazy[2*nd+1].mask|lazy[nd].mask);
  115. 		}
  116. 		lazy[nd].mask=0;
  117. 		lazy[nd].p=1;
  118. 	}
  119. 	if(s>r||e<l||s>e)
  120. 		return {1,0};
  121. 	if(s>=l&&e<=r)
  122. 	{
  123. 		return {t[nd].p,t[nd].mask};
  124. 	}
  125. 	int m=s+(e-s)/2;
  126. 	pair<ll,ll>p1,p2,p;
  127. 	p1=q(2*nd,s,m,l,r);
  128. 	p2=q(2*nd+1,m+1,e,l,r);
  129. 	p.first=(p1.first*p2.first)%MOD;
  130. 	p.second=(p2.second|p1.second);
  131. 	return p;
  132. }
  133. int main()
  134. {
  135. 	ios_base::sync_with_stdio(0);
  136. 	cin.tie(0);
  137. 	sieve();
  138. 	int n,m,i,j,k;
  139. 	cin>>n>>m;
  140. 	for(i=1;i<=n;++i)
  141. 		cin>>a[i];
  142.  
  143. 	init(1,1,n);
  144. 	while(m--)
  145. 	{
  146. 		string str;
  147. 		cin>>str;
  148. 		if(str[0]=='M')
  149. 		{
  150. 			int l,r,val;
  151. 			cin>>l>>r>>val;
  152. 			upd(1,1,n,l,r,val);
  153. 		}
  154. 		else
  155. 		{
  156. 			ll l,r;
  157. 			cin>>l>>r;
  158. 			pair<ll,ll>p=q(1,1,n,l,r);
  159. 			ll msk=p.second;
  160. 			ll ans=p.first;
  161. 			ll pro=1;
  162. 			ll prod=1;
  163. 			while(msk)
  164. 			{
  165. 				int posn=(int)log2(msk&-msk);
  166. 				prod=(prod*(primes[posn]-1))%MOD;
  167. 				pro=(pro*(primes[posn]))%MOD;
  168. 				msk-=(1<<posn);
  169. 			}
  170. 			ans=(ans*prod)%MOD;
  171. 			pro=pwr(pro,MOD-2);
  172. 			ans=(ans*pro)%MOD;
  173. 			cout<<ans<<"\n";
  174. 		}
  175. 	}
  176. 	// your code goes here
  177. 	return 0;
  178. }
Success #stdin #stdout 0s 66944KB
comments (?)
stdin
copy 
4 4
5 9 1 2
TOTIENT 3 3
TOTIENT 3 4
MULTIPLY 4 4 3
TOTIENT 4 4
stdout
copy 
1
1
2
https://ideone.com/5ijuXg
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 years ago
visibility:
secret

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!