fork download 
  1. /*
  2. 	Solution By : Amrutansu Garanaik
  3. 	Codechef id : dragonemperor
  4. */
  5. #include<stdio.h>
  6. #define MAX 10009
  7. #define MOD 1000000007
  8. typedef long long ll;
  9. ll factor[101][25];
  10. ll input[MAX][25];
  11. ll primes[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};
  12. void preprocess()
  13. {		
  14. 	for(int i=0;i<101;i++)
  15. 	for(int j=0;j<25;j++)
  16. 		factor[i][j]=0;
  17. 	for(int i=1;i<101;i++)
  18. 	{
  19. 		ll num=i;
  20. 		for(int j=0;j<25;j++)
  21. 		{
  22. 			int c=0;
  23. 			while(num%primes[j]==0)
  24. 			{
  25. 				c++;
  26. 				num/=primes[j];
  27. 			}
  28. 			factor[i][j]=c;
  29. 		}		
  30. 	}
  31. }
  32. void update(int i,int j,int val)
  33. {
  34. 	while(i<MAX)
  35. 	{
  36. 		input[i][j]+=val;
  37. 		i+=(i&-i);
  38. 	}
  39. }
  40. ll sum(int i,int j)
  41. {
  42. 	ll s=0;
  43. 	while(i>0)
  44. 	{
  45. 		s+=input[i][j];
  46. 		i-=(i&-i);
  47. 	}
  48. 	return s;
  49. }
  50. ll expo(ll base,ll power)
  51. {
  52. 	if(power==0)
  53. 		return 1;
  54. 	if(power==1)
  55. 		return base;
  56. 	ll result=1;
  57. 	while(power)
  58. 	{
  59. 		if(power&1)
  60. 			result=(result*base)%MOD;
  61. 		base=(base*base)%MOD;
  62. 		power>>=1;
  63. 	}
  64. 	return result%MOD;
  65. }
  66. int main()
  67. {
  68. 	ll test,n,temp,q,a,b,result,fact;
  69. 	preprocess();
  70. 	scanf("%lld",&test);
  71. 	while(test--)
  72. 	{
  73. 		for(int i=0;i<MAX;i++)
  74. 		for(int j=0;j<25;j++)
  75. 			input[i][j]=0;
  76.  
  77. 		scanf("%lld",&n);
  78. 		for(int i=0;i<n;i++)
  79. 		{
  80. 			scanf("%lld",&temp);
  81. 			for(int j=0;j<25;j++)
  82. 			{
  83. 				update(i+1,j,factor[temp][j]);
  84. 			}
  85. 		}
  86. 		scanf("%lld",&q);
  87. 		while(q--)
  88. 		{
  89. 			scanf("%lld%lld",&a,&b);
  90. 			result=1;
  91. 			fact=1;
  92. 			for(int i=0;i<25;i++)
  93. 			{
  94. 				temp=sum(b,i)-sum(a-1,i);
  95. 				result=result*(expo(primes[i],temp));
  96. 				result%=MOD;
  97. 				fact*=(temp+1);
  98. 				fact%=MOD;
  99. 			}
  100. 			printf("%lld %lld\n",result,fact);
  101. 		}
  102. 	}
  103. 	return 0;
  104. }
Success #stdin #stdout 0s 5072KB
comments ()
stdin 
1
5
1 2 3 4 5
2
2 3
1 5
stdout 
6 4
120 16
https://ideone.com/tOlVhs
language:
C++14 (gcc 8.3)
created:
9 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!