fork(1) download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3.  
  4. const int N = int(1e6) + 2;
  5.  
  6. int n, x;
  7. int a[N];
  8. long long s[N], c[N];
  9. long long ans;
  10.  
  11. int main()
  12. {
  13. 	freopen("input.txt", "rt", stdin);
  14. 	freopen("output.txt", "wt", stdout);
  15.  
  16. 	scanf("%d", &n);
  17.  
  18. 	for (int i = 0; i < n; i++)
  19. 	{
  20. 		scanf("%d", &x);
  21.  
  22. 		a[x]++;
  23. 	}
  24.  
  25. 	for (long long i = 1; i <= n; i++)
  26. 	{
  27. 		c[i] = c[i - 1] + a[i];
  28. 		s[i] = s[i - 1] + a[i] * i;
  29. 	}
  30.  
  31. 	for (int i = 1; i <= n; i++)
  32. 	{
  33. 		ans += s[i - 1] * a[i];
  34.  
  35. 		for (int j = i; j <= n; j += i)
  36. 		{
  37. 			int k = std::min(n, j + i - 1);
  38.  
  39. 			ans += (s[k] - s[j - 1] - (c[k] - c[j - 1]) * j) * a[i];
  40. 		}
  41. 	}
  42.  
  43. 	std::cout << ans;
  44.  
  45. 	return 0;
  46. }
Success #stdin #stdout 0s 34768KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9c52m5
BelOI 2017-2018 Semifinal, Day 1, Task 3
language:
C++ (gcc 8.3)
created:
6 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!