fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. int mod = 1e9 + 7;
  5. long long ltn(int a, int n, int m){
  6.     long long r=0;
  7.     for(;n>0;n>>=1,a=(a+a)%m)if(n&1)r=(r+a)%m; return r;
  8. }
  9. long long lltn(int a, int n, int m){
  10.     long long r=1;
  11.     a%=m;
  12.     for(;n>0;n>>=1,a=ltn(a,a,m))if(n&1)r=ltn(r,a,m);return r;
  13. }
  14.  
  15. signed main() 
  16. {
  17. 	// freopen("bhlt_bai9.inp", "r", stdin);
  18. 	// freopen("bhlt_bai9.out", "w", stdout);
  19.     long long n, x, a[1000005], b[1000005], r[1000005], mx = 0; cin >> n;
  20. 	memset(r, 0, sizeof(r));
  21.     for(int i = 0; i < n; i++){
  22.       cin >> x;
  23.       a[x]++;
  24.       mx = max(mx, x);
  25.     }
  26.     for(int i = 1; i <= mx; i++){
  27.       for(int j = i; j <= mx; j += i){
  28.         b[i] += a[j];
  29.       }
  30.     }
  31.  
  32.     for(int i = mx; i > 0; i--){
  33.     	r[i] = lltn(2, b[i], mod) - 1;
  34.       for(int j = i + i; j <= mx; j+=i){
  35.         r[i] -= r[j];
  36.       }
  37.  
  38.     }
  39.     cout << r[1];
  40.  
  41. }
  42.  
Success #stdin #stdout 0.01s 12508KB
comments (?)
stdin
copy 
3
1 2 2
stdout
copy 
4
https://ideone.com/HOisa1
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!