fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int MAXN = 200005;
  8. int spf[MAXN];
  9.  
  10. void sieve() {
  11.     for (int i = 1; i < MAXN; i++) spf[i] = i;
  12.     for (int i = 2; i * i < MAXN; i++) {
  13.         if (spf[i] == i) {
  14.             for (int j = i * i; j < MAXN; j += i) {
  15.                 if (spf[j] == j) spf[j] = i;
  16.             }
  17.         }
  18.     }
  19. }
  20.  
  21. void solve() {
  22.     int n, k;
  23.     if (!(cin >> n >> k)) return;
  24.     vector<int> a(n);
  25.     for (int i = 0; i < n; i++) {
  26.         cin >> a[i];
  27.     }
  28.  
  29.     vector<long long> g(n + 1, 0);
  30.     for (int i = k + 1; i <= n; i++) {
  31.         long long min_ops = -1;
  32.         int temp = i;
  33.         while (temp > 1) {
  34.             int p = spf[temp];
  35.             long long ops = 1 + (long long)p * g[i / p];
  36.             if (min_ops == -1 || ops < min_ops) {
  37.                 min_ops = ops;
  38.             }
  39.             while (temp % p == 0) temp /= p;
  40.         }
  41.         g[i] = min_ops;
  42.     }
  43.  
  44.     long long ans = 0;
  45.     for (int i = 0; i < n; i++) {
  46.         ans += g[a[i]];
  47.     }
  48.  
  49.     cout << ans << "\n";
  50. }
  51.  
  52. int main() {
  53.     ios_base::sync_with_stdio(false);
  54.     cin.tie(NULL);
  55.     sieve();
  56.     int t;
  57.     if (cin >> t) {
  58.         while (t--) {
  59.             solve();
  60.         }
  61.     }
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
6
1 1
1
6 2
6 6 4 3 2 1
8 1
8 6 4 3 2 1 8 6
12 3
12 10 9 8 7 6 5 4 3 2 1 12
10 9
10 9 8 7 6 5 4 3 2 1
5 5
5 4 3 2 1
stdout
copy 
0
4
25
15
1
0
https://ideone.com/TuX7UX
language:
C++14 (gcc 8.3)
created:
1 day 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!