fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <map>
  5. #include <numeric>
  6. #include <algorithm>
  7.  
  8. using namespace std;
  9.  
  10. typedef long long ll;
  11.  
  12. const int MOD = 1e9 + 7;
  13.  
  14. // Function for modular exponentiation (b^e % MOD)
  15. ll power(ll base, ll exp) {
  16.     ll res = 1;
  17.     base %= MOD;
  18.     while (exp > 0) {
  19.         if (exp % 2 == 1) res = (res * base) % MOD;
  20.         base = (base * base) % MOD;
  21.         exp /= 2;
  22.     }
  23.     return res;
  24. }
  25.  
  26. // Function to compute modular inverse of n under modulo MOD
  27. ll modInverse(ll n) {
  28.     return power(n, MOD - 2);
  29. }
  30.  
  31. // Precompute factorials up to a small limit (max exponent will be ~log2(10^14) < 50)
  32. vector<ll> fact(61);
  33.  
  34. void precompute_factorials() {
  35.     fact[0] = 1;
  36.     for (int i = 1; i <= 60; i++) {
  37.         fact[i] = (fact[i - 1] * i) % MOD;
  38.     }
  39. }
  40.  
  41. // Calculates C(N + k - 1, k) for large N
  42. ll combinations_large_n(ll N, int k) {
  43.     if (k == 0) return 1;
  44.     if (k < 0) return 0;
  45.  
  46.     ll n_mod = N % MOD;
  47.     ll num = 1;
  48.     for (int i = 0; i < k; ++i) {
  49.         num = (num * ((n_mod + i) % MOD)) % MOD;
  50.     }
  51.  
  52.     ll den_inv = modInverse(fact[k]);
  53.     return (num * den_inv) % MOD;
  54. }
  55.  
  56. // Function to get prime factorization of a number
  57. map<ll, int> get_prime_factorization(ll n) {
  58.     map<ll, int> factors;
  59.     for (ll i = 2; i * i <= n; ++i) {
  60.         while (n % i == 0) {
  61.             factors[i]++;
  62.             n /= i;
  63.         }
  64.     }
  65.     if (n > 1) {
  66.         factors[n]++;
  67.     }
  68.     return factors;
  69. }
  70.  
  71. // Calculates the number of ways to form 'num' by multiplying N integers
  72. ll calculate_ways(ll num, ll N, map<ll, ll>& memo) {
  73.     if (memo.count(num)) {
  74.         return memo[num];
  75.     }
  76.  
  77.     map<ll, int> factors = get_prime_factorization(num);
  78.     ll ans = 1;
  79.     for (auto const& [prime, count] : factors) {
  80.         ans = (ans * combinations_large_n(N, count)) % MOD;
  81.     }
  82.     return memo[num] = ans;
  83. }
  84.  
  85. void solve(int case_num) {
  86.     ll N, A, B;
  87.     cin >> N >> A >> B;
  88.  
  89.     // Find all divisors of B
  90.     vector<ll> divisors;
  91.     for (ll i = 1; i * i <= B; ++i) {
  92.         if (B % i == 0) {
  93.             divisors.push_back(i);
  94.             if (i * i != B) {
  95.                 divisors.push_back(B / i);
  96.             }
  97.         }
  98.     }
  99.  
  100.     ll total_ways = 0;
  101.     map<ll, ll> memo; // Memoization for calculate_ways
  102.  
  103.     for (ll d : divisors) {
  104.         if (d <= A) {
  105.             ll ways1 = calculate_ways(d, N, memo);
  106.             ll ways2 = calculate_ways(B / d, N, memo);
  107.             total_ways = (total_ways + (ways1 * ways2) % MOD) % MOD;
  108.         }
  109.     }
  110.  
  111.     cout << "Case #" << case_num << ": " << total_ways << endl;
  112. }
  113.  
  114. int main() {
  115.     ios_base::sync_with_stdio(false);
  116.     cin.tie(NULL);
  117.  
  118.     precompute_factorials();
  119.  
  120.     int T;
  121.     cin >> T;
  122.     for (int i = 1; i <= T; ++i) {
  123.         solve(i);
  124.     }
  125.  
  126.     return 0;
  127. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
4
3 1 7
2 10 15
2 1000 21
50 50000 3628800
stdout
copy 
Case #1: 3
Case #2: 12
Case #3: 16
Case #4: 229471373
https://ideone.com/Up8S1a
language:
C++ (gcc 8.3)
created:
16 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!