fork(12) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int MAXN = 100005;
  5.  
  6. long long f[MAXN];
  7. long long cum[MAXN];
  8. int n,m,x;
  9. long long ans = 0;
  10.  
  11. void pre(){
  12. 	for(int i = 0; i<MAXN; i++){
  13. 		f[i] = cum[i] = 0;
  14. 	}
  15. }
  16.  
  17. void post(){
  18. 	cum[0] = f[0];
  19. 	for(int i = 1; i<MAXN; i++){
  20. 		cum[i] = cum[i-1] + f[i];
  21. 	}
  22. }
  23.  
  24. void solve(){
  25. 	cin>>n>>m>>x;
  26. 	pre();
  27. 	int t;
  28. 	for(int i = 0; i<n; i++){
  29. 		cin>>t;
  30. 		f[t%m]++;
  31. 	}
  32. 	post();
  33. 	ans = 0;
  34. 	for(int i = 0; i<m; i++){
  35. 		int z0 = (m - i)%m;
  36. 		int zx = (x - i + m)%m;
  37. 		if(z0<=zx){
  38. 			ans += f[i]*(cum[zx] - cum[z0]+f[z0]);
  39. 		}else{
  40. 			ans += f[i]*(cum[m-1] - cum[z0] + f[z0] + cum[zx]);
  41. 		}
  42. 	}
  43.  
  44. 	cout<<ans<<endl;
  45. }
  46.  
  47. int main() {
  48. 	int t;
  49. 	cin>>t;
  50. 	while(t--) solve();
  51. 	return 0;
  52. }
Success #stdin #stdout 0s 4976KB
comments (?)
stdin
copy 
2
3  5  3
1  2  3
4  7  4
31  12  11  17
stdout
copy 
6
12
https://ideone.com/FeFZ9X
language:
C++14 (gcc 8.3)
created:
8 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!