fork(29) download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. typedef long long int ll;
  4. typedef pair < int , int > p;
  5. #define rep(i,a,n)  for(int i = a; i < n; i++)
  6. const int mod = 1000003;
  7. const int N = 2e6+5;
  8. int h[N] = {0}, sum[N] = {0};
  9.  
  10. void solve(){
  11.     int n, i, num;int ele = 0;
  12.     int ans(0);
  13.     cin >> n;
  14.  
  15.     rep(i,0,n)cin >> num, h[num]++, sum[num]++;
  16.     rep(i,1,N)sum[i] += sum[i-1];
  17.     for(int i = 1; i < N; i++){
  18.         if(h[i]){
  19.         	ele = 0;
  20.         	for(int j = i; j < N; j += i){
  21. 	            ans = (ans % mod + ((j / i) * 1LL * h[i] * h[j]) % mod) % mod;
  22. 	            if(i == j || i == 1)continue;
  23. 	           ans =(ans % mod + ( ((j-1) / i) * 1LL * (sum[j-1] - sum[j - i]) * (h[i])) % mod ) % mod;
  24. 			}
  25.         }
  26.         h[i] = 0;
  27.         sum[i] = 0;
  28.     }
  29.     cout << ans << '\n';
  30. }
  31. signed main(){
  32.     ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
  33.         int t;
  34.         cin >> t;
  35.         while(t--)solve();
  36.  
  37.     return 0;
  38. }
Success #stdin #stdout 0.05s 19004KB
comments (?)
stdin
copy 
1
5
1 5 4 2 3
stdout
copy 
27
https://ideone.com/x0baVk
language:
C++14 (gcc 8.3)
created:
4 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!