Statement
This question is based on bonus of this problem.
We need to count such triple $$$(a, b, c)$$$ that satisfy $$$(0 \leq a + b + c \leq S)$$$ and $$$(0 \leq a \times b \times c \leq T)$$$ and $$$min(a, b, c) \geq 0$$$
Since the result may be very big, you can either use bignum or modulo $$$10^9 + 7$$$ for convention
Notice that:
- $$$(0, 0, 1) \neq (0, 1, 0) \neq (1, 0, 0)$$$
Constraint:
$$$0 \leq S, T \leq 10^{18}$$$
$$$0 \leq a, b, c$$$
No Time Limit. But expect to be 10 seconds
Memory Limit: 1Gb
Input:
- A single line contain only two positive 60-bit integers $$$S$$$ and $$$T$$$ ($$$0 \leq S, T \leq 10^{18}$$$)
Output:
- Print a single integer, the number of positive tuple satisfy mathematical condition
Example:
Example 0
Input:
0 0
Output:
1
Explain:
(0, 0, 0)
Example 1
Input:
1 1
Output:
4
Explain:
(0, 0, 0)
(0, 0, 1)
(0, 1, 0)
(1, 0, 0)
Example 2
Input:
10 10
Output:
213
Example 3
Input:
100 100
Output:
16616
Example 4
Input:
1000 1000
Output:
1530920
Example 5
Input:
10000 10000
Output:
150511618
Example 6
Input:
100000 100000
Full Output:
15007668845
Output Modulo 1e9 + 7:
7668740
Example 7
Input:
1000000 1000000
Full Output:
1500107530589
Output Modulo 1e9 + 7:
107520089
Example 8
Input:
10000000 10000000
Full Output:
150001436760246
Output Modulo 1e9 + 7:
435710239
Example 9
Input:
100000000 100000000
Full Output:
15000018512473629
Output Modulo 1e9 + 7:
407473503
Example 10
Input:
1000000000 1000000000
Full Output:
1500000231875375222
Output Modulo 1e9 + 7:
375373675
Example 11
Input:
10000000000 10000000000
Full Output:
?????????????????????
Output Modulo 1e9 + 7:
786369931
Example 12
Input:
100000000000 100000000000
Full Output:
??????????????????????
Output Modulo 1e9 + 7:
72345276
Example 13
Input:
1000000000000 1000000000000
Full Output:
???????????????????????
Output Modulo 1e9 + 7:
173128245
Example 14
Input:
10000000000000 10000000000000
Full Output:
???????????????????????
Output Modulo 1e9 + 7:
144115209
Example 15
Input:
100000000000000 100000000000000
Full Output:
???????????????????????
Output Modulo 1e9 + 7:
607035370
Current best known algorithm
Complexity $$$O(T^{\frac{2}{3}}$$$ time — $$$O(1)$$$ space
Query for $$$(0 \leq S \leq 10^{18}, 0 \leq T \leq 10^{12})$$$ in under $$$830ms$$$
Code
/// @title: Count non negative integer tuple (a, b, c) satisfied (sum <= S) and (product <= T)
/// @testing: for large S <= 1e18, T <= 1e12
/// > in O(T^(2/3)) time complexity = 830ms codeforces = 310ms ideone
/// > in O(const) memory complexity
/// > in O(3700Mb) code memory in 200 lines, 4271 characters
///
/// @date: 23/08/2021
/// @link: https://i...content-available-to-author-only...e.com/yMi8tu
/// @author: SPyofgame
/// @lisence: free lisence
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <iostream>
#include <cmath>
typedef long long ll;
const int MOD = 1e9 + 7;
/// ====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====*====
/// Utility function
ll min(ll a, ll b) { return a < b ? a : b; }
ll max(ll a, ll b) { return a > b ? a : b; }
ll square(ll x) { return x * x; }
/// Sum of (1 + 2 + ... + x)
ll natural_sum(ll x)
{
return (x <= 0) ? 0 : x * (x + 1) / 2;
}
/// Sum of (l + (l + 1) + ... + r)
ll natural_sum(ll l, ll r)
{
return (l > r) ? 0 : natural_sum(r) - natural_sum(l - 1);
}
/// Sigma(p = y -> x) floor(n / p) in O(cbrt(n))
/// @link: https://a...content-available-to-author-only...v.org/pdf/1206.3369.pdf
/// @author: Richard Sladkey
ll fastsumdiv(ll y, ll x, ll n)
{
if (y > x) return 0;
ll S = 0;
ll B = n / (x + 1);
ll E = n % (x + 1);
ll D = n / x - B;
ll G = B - x * D;
ll d = 0;
for (; x >= y; --x)
{
E += G;
if (E >= x)
{
D += 1, G -= x, E -= x;
if (E >= x)
{
D += 1, G -= x, E -= x;
if (E >= x) break;
}
}
else if (E < 0)
{
D -= 1, G += x, E += x;
}
G += 2 * D, B += D, S += B;
}
E = n % (x + 1);
D = n / x - B;
G = B - x * D;
for (; x >= y; --x)
{
E += G;
d = E / x;
D += d;
E -= x * d;
G += 2 * D - x * d, B += D, S += B;
}
for (; x >= y; --x)
S += n / x;
return S;
}
/// you can modify to -> Bignum / Modulo / Overflow
void add(ll &res, ll val)
{
val %= MOD;
res += val;
if (res >= MOD) res -= MOD;
}
void sub(ll &res, ll val)
{
val %= MOD;
res -= val;
if (res < 0) res += MOD;
}
/// Count (a, b, c) satisfied
/// { min(a, b, c) >= 0
/// { a + b + c <= S
/// { a * b * c <= T
/// O(cbrt(T)^2) complexity
///
/// @proof: https://m...content-available-to-author-only...e.com/questions/4230187/faster-algorithm-for-counting-non-negative-tripplea-b-c-satisfied-a-b-c
/// @author: SPyofgame
ll solve_ABC(ll S, ll T)
{
const ll cbT = cbrt(T);
/// [1] 0 <= a < b < c && a <= cbrt(T) -> cnt1 * 6
ll cnt1 = 0;
add(cnt1, (S / 2) * S - 2 * natural_sum(S / 2)); /// a = 0
ll k = 1;
for (ll a = 1, upa = min(S, cbT); a <= upa; ++a) /// a > 0 -> count(b < c)
{
ll SSS = S - a;
ll TTT = T / a;
ll KKK = min(SSS / 2, min((ll)sqrt(TTT), TTT / 2 + 1));
/// Binary search for max k satisfy (S - a - k) <= (T / a / k)
ll k = a;
for (ll l = a + 1, r = KKK; l <= r; )
{
ll m = (l + r) >> 1;
ll v = TTT / m;
if (SSS - m <= v)
{
k = m;
l = m + 1;
}
else
{
r = m - 1;
}
}
sub(cnt1, natural_sum(a + 1, KKK));
add(cnt1, SSS * (k - a) - natural_sum(a + 1, k));
add(cnt1, fastsumdiv(k + 1, KKK, TTT));
}
/// [2] 0 <= a < b = c && a <= cbrt(T) -> cnt2 * 3
ll cnt2 = 0;
add(cnt2, S / 2); /// a = 0
for (ll a = 1, upa = min(S, cbT); a <= upa; ++a) /// a > 0 -> count(b = c)
{
add(cnt2, max(0LL, min((S - a) / 2, ll(floor(sqrt(T / a)))) - a));
}
/// [3] 0 <= a = b < c && a <= cbrt(T) -> cnt3 * 3
ll cnt3 = 0;
add(cnt3, S); /// a = 0
for (ll a = 1, upa = min(S / 2, cbT); a <= upa; ++a) /// a > 0 -> count(a < c)
{
add(cnt3, max(0LL, min(S - a - a, T / a / a) - a));
}
/// [4] 0 <= a = b = c && a <= cbrt(T) -> cnt4 * 1
ll cnt4 = 0;
add(cnt4, min(S / 3, cbT) + 1); /// a = b = c >= 0
/// Final result: total counting
ll res = 0;
add(res, cnt1 * 6 + cnt2 * 3 + cnt3 * 3 + cnt4 * 1);
return res;
}
/// Main function
int main()
{
/// Input any number 0 <= S, T <= 1e18
std::cout << solve_ABC(1000000000000000000LL, 1000000000000LL);
return 0;
}