fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #define MOD 1000000007
  5. #define gc getchar_unlocked
  6.  
  7. using namespace std;
  8.  
  9. void scaninp(int &a)
  10. {
  11. 	register int b;
  12. 	a = 0;
  13.  
  14. 	b = gc();
  15.  
  16. 	for (; ((b < 48) || (b > 57)); b = gc());
  17. 	for (; ((b > 47) && (b < 58)); b = gc()) {
  18. 		a = (a << 1) + (a << 3) + b-48;
  19. 	}
  20. }
  21. int power(int a, int b)
  22. {
  23. 	if (b == 0)
  24. 		return 1;
  25. 	if (b == 1)
  26. 		return a;
  27. 	else if (b &1) {
  28. 		int z;
  29. 		z = power(a,b/2);
  30. 		return (z*z*a);
  31. 	} else {
  32. 		int z;
  33. 		z = power(a,b/2);
  34. 		return (z*z);
  35. 	}
  36. }
  37.  
  38. int main() {
  39. 	// your code goes here
  40. 	int tcase,n,q,i,j,k,x,l,ans,t1,temp;
  41. 	double y,z;
  42. 	scaninp(tcase);
  43.  
  44. 	while (tcase--) {
  45. 		scaninp(n);
  46. 		scaninp(q);
  47.  
  48. 		int a[n+1],s[n+1];
  49.  
  50. 		s[0] = 0;
  51.  
  52. 		for (i = 1; i <= n; ++i) {
  53. 			scaninp(a[i]);
  54. 			a[i] = (a[i] + MOD) % MOD;
  55. 			s[i] = (s[i-1] + a[i])%MOD;
  56. 		}
  57.  
  58. 		for (i = 1; i <= q; ++i) {
  59. 			scaninp(x);
  60. 			ans = 0;
  61. 			x = x % MOD;
  62.  
  63. 			for (j = 1; j <=n; ++j) {
  64. 				if (j == 1) {
  65. 					temp = x;
  66. 					t1 = temp;
  67. 				} else if ( j == 2){
  68. 					z = sqrt((double)x);
  69. 					temp = (int)z;
  70. 					t1 = temp;
  71. 				} else {
  72. 					y = (double)1.00/(double)j;
  73. 					z = pow((double)x, y);
  74. 					temp = (int)z;
  75. 					t1 = temp;
  76. 				}
  77.  
  78. 				if (power(temp,j) <= x) {
  79. 					while (power(t1++,j) <= x);
  80. 					t1 = t1 -2;
  81. 				} else {
  82. 					while (power(t1--,j) > x);
  83. 					t1 = t1+1;
  84. 				}
  85.  
  86. 				if (t1 == 1)
  87. 					break;
  88.  
  89. 				ans = (ans + (t1 * a[j])%MOD)%MOD;
  90. 			}
  91. 			if (j < n)
  92. 				ans = (ans + s[n]-s[j]+MOD)%MOD;
  93. 			printf("%d\n", ans);
  94. 		}
  95. 	}
  96. 	return 0;
  97. }
Success #stdin #stdout 0s 3344KB
comments (?)
stdin
copy 
1
3 1
4 5 6
10000000000000000
stdout
copy 
-795135997
https://ideone.com/XF3uAs
language:
C++ (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!