fork download
copy 
  1.  
  2. #include <iostream>
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. static const int MAXA = 1000000;
  7. static const int MOD  = 1000000007;
  8.  
  9. // fast exponentiation
  10. long long modexp(long long b, long long e){
  11.     long long r=1;
  12.     while(e){
  13.         if(e&1) r = (r*b)%MOD;
  14.         b=(b*b)%MOD;
  15.         e>>=1;
  16.     }
  17.     return r;
  18. }
  19.  
  20. int main(){
  21.     ios::sync_with_stdio(false);
  22.     cin.tie(nullptr);
  23.  
  24.     int n; 
  25.     cin >> n;
  26.     vector<int> freq(MAXA+1,0);
  27.     for(int i=0;i<n;i++){
  28.         int a; 
  29.         cin>>a;
  30.         freq[a]++;
  31.     }
  32.  
  33.     // 1) Compute C[i] = how many a_j divisible by i
  34.     vector<int> C(MAXA+1,0);
  35.     for(int i=1;i<=MAXA;i++){
  36.         for(int j=i;j<=MAXA;j+=i)
  37.             C[i] += freq[j];
  38.     }
  39.  
  40.     // 2) Compute S[i] = i * f(C[i]) = i * (C[i] * 2^(C[i]-1))
  41.     vector<int> S(MAXA+1,0);
  42.     for(int i=2;i<=MAXA;i++){
  43.         int c = C[i];
  44.         if(c==0) continue;
  45.         // f(c) = c * 2^(c-1) % MOD
  46.         long long fc = ( (long long)c * modexp(2, c-1) ) % MOD;
  47.         S[i] = (long long)i * fc % MOD;
  48.     }
  49.  
  50.     // 3) Inclusion–exclusion downward to get A[i]
  51.     vector<int> A(MAXA+1,0);
  52.     long long answer = 0;
  53.     for(int i=MAXA; i>=2; --i){
  54.         long long ai = S[i];
  55.         // subtract off multiples
  56.         for(int j = 2*i; j <= MAXA; j += i){
  57.             ai = (ai - A[j] + MOD) % MOD;
  58.         }
  59.         A[i] = ai;
  60.         answer = (answer + ai) % MOD;
  61.     }
  62.  
  63.     cout << answer << "\n";
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0.08s 18744KB
comments (?)
stdin
copy 
3
3 3 1
stdout
copy 
12
https://ideone.com/4L2mL3
language:
C++ (gcc 8.3)
created:
16 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!