fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define pb push_back
  3. #define mp make_pair
  4. #define ll long long
  5. #define f(i, x, y) for(int i = x; i < y; i++)
  6. #define int long long
  7. const  int mod = 1e9 + 7;
  8. const int inf = 1e5;
  9. using namespace std;
  10.  
  11. main()
  12. {
  13.     int n; cin>>n;
  14.     int arr[n+1];
  15.     int gcd[1000001];
  16.     memset(gcd, 0, sizeof(gcd));
  17.  
  18.     f(i, 1, n+1)
  19.     {
  20.         cin>>arr[i];
  21.     }
  22.  
  23.     int p2[1000001];
  24.     p2[0] = 1;
  25.     f(i, 1, 1000001)
  26.         p2[i] = (p2[i-1] * 2) % mod;
  27.  
  28.     f(i, 1, n+1)
  29.     {
  30.         int x = sqrt(arr[i]);
  31.         gcd[arr[i]]++;
  32.  
  33.         f(j, 2, x+1)
  34.         {
  35.             if(arr[i] % j ==0)
  36.             {
  37.                 gcd[j]++;
  38.                 gcd[arr[i]/j]++;
  39.             }
  40.         }
  41.         if(x * x == arr[i])
  42.             gcd[x]--;
  43.     }
  44.  
  45.  
  46. /*    f(i, 2, 1000001)
  47.     {
  48.         for(int j = 2; i * j <= 1000000; j++)
  49.             gcd[i] += gcd[i*j];
  50.     }
  51. */    
  52.     int ans[1000001];
  53.     memset(ans, 0, sizeof(ans));
  54.  
  55.     for(int i = 1000000; i > 1; i--) 
  56.     {
  57.         ans[i] = gcd[i] * p2[max(gcd[i] - 1, (int)0)];
  58.  
  59.         for(int j = 2; i * j <= 1000000; j++)
  60.             ans[i] = (ans[i] - ans[i*j] + mod) % mod;
  61.  
  62.     }
  63.  
  64.     int res = 0;
  65.  
  66.     f(i, 2, 1000001)
  67.         res = ((ans[i] * i) % mod + res) % mod;
  68.     cout<<res;    
  69. }
Success #stdin #stdout 0.1s 39376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tJhWMt
language:
C++14 (gcc 8.3)
created:
7 years 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!