fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. static const int MAXA = 1000000;
  5. static const int MOD  = 1000000007;
  6.  
  7. int add(int x,int y){ x+=y; if(x>=MOD) x-=MOD; return x; }
  8. int mul(ll x,ll y){ return int((x*y)%MOD); }
  9.  
  10. int main(){
  11.     ios::sync_with_stdio(false);
  12.     cin.tie(nullptr);
  13.  
  14.     int n; 
  15.     cin >> n;
  16.     vector<int> freq(MAXA+1, 0);
  17.     for(int i = 0; i < n; i++){
  18.         int a; 
  19.         cin >> a;
  20.         freq[a]++;
  21.     }
  22.  
  23.     // 1) Sieve phi up to MAXA
  24.     vector<int> phi(MAXA+1);
  25.     for(int i = 0; i <= MAXA; i++) 
  26.         phi[i] = i;
  27.     for(int p = 2; p <= MAXA; p++){
  28.         if(phi[p] == p){
  29.             for(int j = p; j <= MAXA; j += p){
  30.                 phi[j] -= phi[j] / p;
  31.             }
  32.         }
  33.     }
  34.  
  35.     // 2) For each k, count how many a_i are multiples of k
  36.     vector<int> cnt(MAXA+1, 0);
  37.     for(int k = 1; k <= MAXA; k++){
  38.         for(int j = k; j <= MAXA; j += k){
  39.             cnt[k] += freq[j];
  40.         }
  41.     }
  42.  
  43.     // 3) Precompute powers of two mod MOD
  44.     vector<int> pw2(n+1, 1);
  45.     for(int i = 1; i <= n; i++){
  46.         pw2[i] = add(pw2[i-1], pw2[i-1]);  // = pw2[i-1]*2 % MOD
  47.     }
  48.  
  49.     // 4) Sum up result
  50.     ll ans = 0;
  51.     for(int k = 2; k <= MAXA; k++){
  52.         int c = cnt[k];
  53.         if(c == 0) continue;
  54.         // sum_{nonempty subsets S of size c} |S| = c * 2^(c-1)
  55.         int ways = mul(c, pw2[c-1]);
  56.         ans = (ans + (ll)phi[k] * ways) % MOD;
  57.     }
  58.  
  59.     cout << ans << "\n";
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0.06s 14760KB
comments (?)
stdin
copy 
3
3 3 1
stdout
copy 
8
https://ideone.com/2bHtnf
language:
C++ (gcc 8.3)
created:
17 hours 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!