fork download 
  1. #include <bits/stdc++.h>
  2. #define C make_pair
  3. #define ll long long
  4. #define all(a) a.begin(),a.end()
  5. #define name "task"
  6. #define ln "\n"
  7. using namespace std;
  8. const ll N=1e6+9,maxN=3*1e5+9;
  9. ll n,m,q;
  10. ll a1,b1,c1;
  11. ll f1[N],f2[N],f[N];
  12. void findmod(){
  13. 	f1[0]=f2[0]=f[0]=1;
  14. 	for(int i=1;i<=maxN;++i){
  15. 		if(i%3==1){
  16. 			f[i]=f[i-1];
  17. 			f1[i]=f1[i-1]+1;
  18. 			f2[i]=f2[i-1];
  19. 		} else if(i%3==2){
  20. 			f[i]=f[i-1];
  21. 			f1[i]=f1[i-1];
  22. 			f2[i]=f2[i-1]+1;
  23. 		} else if(i%3==0){
  24. 			f[i]=f[i-1]+1;
  25. 			f1[i]=f1[i-1];
  26. 			f2[i]=f2[i-1];
  27. 		}
  28. 	}
  29. }
  30. ll power(ll a,ll b,ll mod){
  31. 	if(b==0)
  32. 		return 1;
  33. 	if(b==1)
  34. 		return a;
  35. 	ll ans=1;
  36. 	while(b){
  37. 		if(b%2==1) ans=((ans%mod)*(a%mod))%mod;
  38. 		a=((a%mod)*(a%mod))%mod;
  39. 		b>>=1;
  40. 	}
  41. 	return ans%mod;
  42. }
  43. void solve(){
  44. 	findmod();
  45. 	cin>>n>>m>>q;
  46. 	cin>>a1>>b1>>c1;
  47. 	ll x1=power(c1,a1,m-1)%(m-1);
  48. 	ll pw1=power(b1,x1,m)%m;
  49.  
  50. 	ll x2=power(a1,b1,m-1)%(m-1);
  51. 	ll pw2=power(c1,x2,m)%m;
  52.  
  53. 	ll x3=power(b1,c1,m-1)%(m-1);
  54. 	ll pw3=power(a1,x3,m)%m;
  55. 	//cout<<pw1<<" "<<pw2<<" "<<pw3<<ln;
  56. 	for(int i=0;i<q;++i){
  57. 		ll ans=0;
  58. 		ll l,r; cin>>l>>r;
  59. 		ans+=(f[r]-f[l-1])*pw1;
  60. 		ans+=(f2[r]-f2[l-1])*pw2;
  61. 		ans+=(f1[r]-f1[l-1])*pw3;
  62. 		//cout<<(f[r]-f[l-1])<<" "<<(f1[r]-f1[l-1])<<" "<<(f2[r]-f2[l-1])<<ln;
  63. 		cout<<ans<<ln;
  64. 	}
  65. }
  66. int main(){
  67. 	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  68. 	if(fopen(name".inp","r")){
  69. 		freopen(name".inp","r",stdin);
  70. 		freopen(name".out","w",stdout);
  71. 	}
  72. 	solve();
  73. }
  74.  
Success #stdin #stdout 0.01s 17132KB
comments (?)
stdin 
10 37 3
36 29 98
1 10
5 8
4 4
stdout 
225
64
36
https://ideone.com/BVVLlj
language:
C++14 (gcc 8.3)
created:
2 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!