fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using int64 = long long;
  4. const int MOD = 1000000007;
  5.  
  6. // Recursive Double DP with memoization:
  7. // F(i, g) = F(i+1, g) + F(i+1, gcd(g, a[i])) * fval[a[i]]
  8. // Base: i == n: return (g > 0 ? inv[g] : 0)
  9.  
  10. int n, A;
  11. vector<int> a;
  12. vector<int> phi;
  13. vector<int64> fval, invv;
  14. vector<unordered_map<int,int64>> memo;
  15.  
  16. int64 mod_pow(int64 x, int64 e) {
  17.     int64 r = 1;
  18.     while (e) {
  19.         if (e & 1) r = r * x % MOD;
  20.         x = x * x % MOD;
  21.         e >>= 1;
  22.     }
  23.     return r;
  24. }
  25.  
  26. int64 dfs(int idx, int g) {
  27.     if (idx == n) {
  28.         return g > 0 ? invv[g] : 0;
  29.     }
  30.     auto &mp = memo[idx];
  31.     auto it = mp.find(g);
  32.     if (it != mp.end()) return it->second;
  33.  
  34.     // Skip a[idx]
  35.     int64 res = dfs(idx + 1, g);
  36.     // Take a[idx]
  37.     int ng = (g == 0 ? a[idx] : __gcd(g, a[idx]));
  38.     res = (res + dfs(idx + 1, ng) * fval[a[idx]] % MOD) % MOD;
  39.  
  40.     return mp[g] = res;
  41. }
  42.  
  43. int main() {
  44.     ios::sync_with_stdio(false);
  45.     cin.tie(nullptr);
  46.  
  47.     cin >> n;
  48.     a.resize(n);
  49.     A = 0;
  50.     for (int i = 0; i < n; i++) {
  51.         cin >> a[i];
  52.         A = max(A, a[i]);
  53.     }
  54.  
  55.     // Compute phi
  56.     phi.resize(A+1);
  57.     iota(phi.begin(), phi.end(), 0);
  58.     for (int i = 2; i <= A; i++) {
  59.         if (phi[i] == i) {
  60.             for (int j = i; j <= A; j += i)
  61.                 phi[j] -= phi[j] / i;
  62.         }
  63.     }
  64.  
  65.     // Compute inverses
  66.     invv.resize(A+1);
  67.     for (int i = 1; i <= A; i++)
  68.         invv[i] = mod_pow(i, MOD - 2);
  69.  
  70.     // Compute fval = a_i * inv(phi[a_i]) % MOD
  71.     fval.resize(A+1);
  72.     for (int i = 1; i <= A; i++)
  73.         fval[i] = (int64)i * invv[phi[i]] % MOD;
  74.  
  75.     // Prepare memo
  76.     memo.assign(n, unordered_map<int,int64>());
  77.     for (auto &m : memo) m.reserve(1024);
  78.  
  79.     // Get result from recursion
  80.     cout << dfs(0, 0) << '\n';
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
4
1 2 3 4
stdout
copy 
500000042
https://ideone.com/9QqjjI
language:
C++ (gcc 8.3)
created:
2 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!