fork download
  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
stdin
5
1 2 3 4 5
4
1 2 3
2 3 4
1 1 1
1 5 287438
stdout
2
2
0
120