fork download
copy 
  1. #include "bits/stdc++.h"
  2.  
  3. #define endl '\n'
  4. #define SZ(v) int((v).size())
  5. using namespace std;
  6. typedef long long ll;
  7. const int N = 1e5 + 7, M = 2 * N;
  8. using vi = vector<int>;
  9.  
  10. int comp[N + 1];
  11. vi primes;
  12. void sieve() {
  13.     for (int i = 2; i <= N; ++i) {
  14.         int &x = comp[i];
  15.         if (!x) primes.emplace_back(x = i);
  16.         for (int j = 0; primes[j] <= N / i; j++) {
  17.             comp[i * primes[j]] = primes[j];
  18.             if (primes[j] >= x) break;
  19.         }
  20.     }
  21. }
  22. int t, n, k;
  23.  
  24. vi taken;
  25. int GCD = 1;
  26.  
  27. int bad[N];
  28.  
  29. //backtracks over all values of y where y's upper k factors are the upper k factors of GCD AND any other factors weren't taken in x
  30. ll test(int v, int pid, int e) {
  31.  
  32.     if (pid >= e || v > n / primes[pid]) return 1;
  33.     ll ans = 0;
  34.     if (!bad[pid]) {
  35.         v *= primes[pid];
  36.         ans += test(v, pid, e);
  37.         v /= primes[pid];
  38.     }
  39.     ans += test(v, pid + 1, e);
  40.     return ans;
  41. }
  42.  
  43. //backtracks over all values of x where x's lower k factors are the lower k factors of GCD
  44. ll all(int v, int pid) {
  45.     if (pid >= SZ(primes) || v > n / primes[pid]) return test(GCD, 0, taken[k] + 1);
  46.     ll ans = 0;
  47.     v *= primes[pid];
  48.     ++bad[pid];
  49.     ans += all(v, pid);
  50.     --bad[pid];
  51.     v /= primes[pid];
  52.     ans += all(v, pid + 1);
  53.     return ans;
  54. }
  55.  
  56. //backtracks over all possible values that have exactly 2k factors
  57. ll take(int pid, int need) {
  58.     if (need == 0) return all(GCD, taken[k - 1]);
  59.     if (pid >= SZ(primes) || GCD > n / primes[pid]) return 0;
  60.     ll ans = 0;
  61.     taken.push_back(pid);
  62.     GCD *= primes[pid];
  63.     ans += take(pid, need - 1);
  64.     GCD /= primes[pid];
  65.     taken.pop_back();
  66.     ans += take(pid + 1, need);
  67.     return ans;
  68. }
  69.  
  70. int main() {
  71.     ios_base::sync_with_stdio(0), cin.tie(0);
  72. #ifdef CLION
  73.     freopen("in", "rt", stdin);
  74. #endif
  75.     sieve();
  76.  
  77.     scanf("%d", &t);
  78.     while (t--) {
  79.         scanf("%d%d", &n, &k);
  80.         if (k > 8) {
  81.             puts("0");
  82.             continue;
  83.         }
  84.         printf("%lld\n", take(0, 2 * k));
  85.     }
  86. }
  87.  
Success #stdin #stdout 0s 4936KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/4lgcAd
language:
C++14 (gcc 8.3)
created:
3 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!