fork download
copy 
  1. #include<stdio.h>
  2. long long inline scan()
  3. {
  4.     long long x=0;
  5.     int c = getchar();
  6.     int neg = 0;
  7.     for(;((c<48 || c>57) && c != '-');c = getchar());
  8.     if(c=='-') {neg=1;c=getchar();}
  9.     for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}
  10.     if(neg) x=-x;
  11.     return x;
  12. }
  13.  
  14. long long exp(long long a,long long b,long long mod)
  15. {
  16.  
  17.     long long result=1;
  18.     while(b)
  19.     {
  20.         if(b%2==1)
  21.         {
  22.             result*= a;
  23.             while(result>=mod)
  24.                 result-=mod;
  25.         }
  26.         b=b>>1;
  27.         a*= a;
  28.         while(a>=mod)
  29.             a-=mod;
  30.     }
  31.     return result;
  32. }
  33. /*
  34. long long exp(int a, int b,long long mod){
  35. long long r;
  36. if(b==0) return 1;
  37. r = exp(a,b/2,mod);
  38. r = (r*r)%mod;
  39. if(b%2) r = (r*a)%mod;
  40. return r;
  41. }
  42. */
  43. int np[100001][26]={0};
  44. int tmp[101][26]={0};
  45. int prime[26]={0};
  46. //int invprime[101];
  47. int main()
  48. {
  49.     int i,j,n,t,k,l,r;
  50.     long long temp,m,ans;
  51.     prime[1]=2;
  52.     prime[2]=3;
  53.     prime[3]=5;
  54.     prime[4]=7;
  55.     prime[5]=11;
  56.     prime[6]=13;
  57.     prime[7]=17;
  58.     prime[8]=19;
  59.     prime[9]=23;
  60.     prime[10]=29;
  61.     prime[11]=31;
  62.     prime[12]=37;
  63.     prime[13]=41;
  64.     prime[14]=43;
  65.     prime[15]=47;
  66.     prime[16]=53;
  67.     prime[17]=59;
  68.     prime[18]=61;
  69.     prime[19]=67;
  70.     prime[20]=71;
  71.     prime[21]=73;
  72.     prime[22]=79;
  73.     prime[23]=83;
  74.     prime[24]=89;
  75.     prime[25]=97;
  76.     for(i=2;i<101;i++)
  77.     {
  78.         k=i;
  79.         temp=1;
  80.         for(j=prime[temp];j*j<=k;)
  81.         {
  82.             while(k%j==0)
  83.             {
  84.                 tmp[i][temp]++;
  85.                 k/=j;
  86.             }
  87.             temp++;
  88.             j=prime[temp];
  89.         }
  90.         if(k>1)
  91.         {
  92.             for(j=1;j<26;j++)
  93.                 if(prime[j]==k)
  94.                     break;
  95.             tmp[i][j]++;
  96.         }
  97.     }
  98.     n=scan();
  99.  
  100.     /*for(i=1;i<=n;i++)
  101.     {
  102.         temp=scan();
  103.         for(j=1;j<101;j++)
  104.         {
  105.             np[i][j]=tmp[temp][j];
  106.         }
  107.     }
  108.  
  109.     for(i=2;i<=n;i++)
  110.         for(j=1;j<101;j++)
  111.             np[i][j]+=np[i-1][j];
  112.     */
  113.     temp=scan();
  114.     for(i=1;i<26;i++)
  115.         np[1][i]=tmp[temp][i];
  116.  
  117.     for(i=2;i<=n;i++)
  118.     {
  119.         temp=scan();
  120.         for(j=1;j<26;j++)
  121.             np[i][j]=np[i-1][j]+tmp[temp][j];
  122.     }
  123.  
  124.     t=scan();
  125.     while(t--)
  126.     {
  127.         l=scan();
  128.         r=scan();
  129.         m=scan();
  130.         if(m==1) printf("0\n");
  131.         else
  132.         {
  133.             ans=1;
  134.             for(i=1;i<26;i++)
  135.             {
  136.                 temp=np[r][i]-np[l-1][i];
  137.                 if(temp)
  138.                     ans=(ans*exp(prime[i],temp,m))%m;
  139.                 if(ans==0) break;
  140.             }
  141.             printf("%lld\n",ans);
  142.         }
  143.     }
  144.     return 0;
  145. }
  146.  
  147.  
  148.  
Success #stdin #stdout 0s 12904KB
comments (?)
stdin
copy 
5
1 2 3 4 5
4
1 2 3
2 3 4
1 1 1
1 5 287438
stdout
copy 
2
2
0
120
https://ideone.com/pawz5b
language:
C++ 4.3.2 (gcc-4.3.2)
created:
12 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!