fork download
copy 
  1.  //...START BY DOING WHAT IS NECESSARY, THEN WHAT IS POSSIBLE AND SUDDENLY YOU ARE DOING THE IMPOSSIBLE... 
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  5. #define pb push_back
  6. typedef long long ll;
  7. #define endl '\n'
  8. #define M 1000000007
  9. bool comp(int x,int y)
  10. {
  11.     return x > y;   
  12. }
  13.  
  14.  
  15. /*..............................code starts here........................*/
  16.  
  17. int pr(int ele,int p)
  18. {
  19.     int count = 0;
  20.     while(ele%p == 0)
  21.     {
  22.         count += 1;
  23.         ele = ele/p;
  24.     }
  25.     return count;
  26. }
  27. ll power(ll no,ll p)
  28. {
  29.     if(p == 1)
  30.     return no;
  31.     if(p == 0)
  32.     return 1;
  33.     ll q = power(no,p/2);
  34.     q = q*q;
  35.     if(p % 2 != 0)
  36.     q = q*no;
  37.     return q;
  38. }
  39. int main() {
  40.     FAST_IO;
  41.     int n;
  42.     cin >> n;
  43.     ll arr[n];
  44.     for(int i=0;i<n;i++)
  45.     cin >> arr[i];
  46.     map<int,vector<int> > mp;
  47.     //map<position,factors of the prime no>
  48.     int prime[25]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
  49.     for(int i=0;i<n;i++)
  50.     {
  51.         vector<int>vec;
  52.         for(int j=0;j<25;j++)
  53.         {
  54.             if(i == 0)
  55.             vec.pb(pr(arr[i],prime[j]));
  56.             else
  57.             vec.pb(mp[i-1][j]+pr(arr[i],prime[j]));
  58.         }
  59.         mp[i] = vec;
  60.     }
  61.  
  62.     int t;
  63.     cin >> t;
  64.     while(t--)
  65.     {
  66.         int l,r,mod;
  67.         cin >> l >> r >> mod;
  68.         int pro = 1;
  69.         //for(int j=l-1;j<r;j++)
  70.         //{
  71.             for(int i =0;i<25;i++)
  72.             {
  73.                 if(l == 1)
  74.                 pro = (pro * power(prime[i],mp[r-1][i]))%mod;
  75.                 else
  76.                 {
  77.                     pro = (pro * power(prime[i],mp[r-1][i]-mp[l-2][i]))%mod;
  78.                     //if(prime[i] == 2 || prime[i] == 3)
  79.                     //cout << mp[r-1][i] << " " << mp[l-1][i] << endl;
  80.                 }
  81.             }
  82.             //count += mp[prime[i],j];
  83.         //}
  84.         cout << pro%mod << endl;
  85.     }
  86. }
  87.  
  88.  
  89.  
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96. //remarks..
  97. /*
  98. 1.seive of erasthanos till n=10000
  99. 2.lcm
  100. 3.power function..dont forget to apply mod if needed
  101. 4.int to string and vice-versa
  102. 5.checking the prime no
  103. 6.pascal triangle implementation
  104. */
  105.  
Time limit exceeded #stdin #stdout 5s 4488KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uDI6ck
language:
C++ (gcc 8.3)
created:
3 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!