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