fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int mx = 200000;
  5. vector<int> lo(mx + 1), pri;
  6.  
  7. int main() {
  8.     for (int x = 2; x <= mx; x++) {
  9.         if (!lo[x]) {
  10.             lo[x] = x;
  11.             pri.push_back(x);
  12.         }
  13.         for (int p : pri) {
  14.             if (p * x > mx) break;
  15.             lo[p * x] = p;
  16.             if (p == lo[x]) break;
  17.         }
  18.     }
  19.     int t;
  20.     cin >> t;
  21.     while (t--) {
  22.         int n, k;
  23.         cin >> n >> k;
  24.         vector<int> a(n);
  25.         for (int &x : a) cin >> x;
  26.  
  27.         const long long inf = LLONG_MAX;
  28.         vector<long long> dp(n + 1, inf);
  29.  
  30.         for (int x = 1; x <= n; x++) {
  31.             if (x <= k) {
  32.                 dp[x] = 0;
  33.                 continue;
  34.             }
  35.             int xx = x;
  36.             while (xx > 1) {
  37.                 int p = lo[xx];
  38.                 dp[x] = min(dp[x], 1 + dp[x / p] * p);
  39.                 xx /= p;
  40.             }
  41.         }
  42.         long long ans = 0;
  43.         for (int x : a) ans += dp[x];
  44.         cout << ans << '\n';
  45.     }
  46. }
  47.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uVsQng
language:
C++ (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!