fork download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define endl "\n"
  5. #define int long long
  6. #define faster() ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  7. const int MOD = 1e9 + 7 ;
  8. const int N = 1e6 + 20 ;
  9.  
  10. vector<int> v(N), cnt(N) , dp(N);
  11. int binExp(int a, int b){
  12.     int res = 1 ;
  13.     a %= MOD ;
  14.     while(b){
  15.         if(b % 2 == 1){
  16.             res *= a;
  17.             res %= MOD ;
  18.         }
  19.         a *= a;
  20.         a %= MOD ;
  21.         b /= 2 ;
  22.     }
  23.     return res % MOD ;
  24. }
  25.  
  26.  
  27. void solve() {
  28.     int n ; cin >> n;
  29.     for(int i = 0 ; i < n ; i++){
  30.         int x ; cin >> x ;
  31.         for(int y = 1 ; y * y <= x ; y++){
  32.             if(x % y == 0){
  33.                 cnt[y]++ ;
  34.                 if(y *y != x) cnt[x/y]++ ;
  35.             }
  36.         }
  37.     }
  38.  
  39.     for(int i = 0 ; i < N; i++){
  40.         if(cnt[i]){
  41.             dp[i] = cnt[i] * binExp(2 , cnt[i] - 1);
  42.             dp[i] %= MOD ;
  43.         }
  44.     }
  45.     int ans = 0 ;
  46.     for(int i = N ; i > 1 ; i--){
  47.         for(int j = 2 * i; j < N ; j += i){
  48.             dp[i] = (dp[i] - dp[j] + MOD) % MOD ;
  49.         }
  50.         ans = (ans + i * dp[i]);
  51.         ans %= MOD ;
  52.     }
  53.     cout << ans << endl;
  54. }
  55.  
  56. signed main() {
  57.     faster();
  58.     int test = 1 ;
  59.     // cin >> test ;
  60.     while(test--)   solve();
  61.     return 0;
  62. }
  63.  
Success #stdin #stdout 0.15s 26436KB
comments (?)
stdin
copy 
4
2 3 4 6
stdout
copy 
39
https://ideone.com/MOqmqT
language:
C++14 (gcc 8.3)
created:
119 days 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!