/// @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^(5/9)) time complexity = 830ms codeforces = 310ms ideone
/// > in O(const) memory complexity
/// > in O(3700Mb) code memory in 200 lines, 4444 characters
///
/// @date: 23/08/2021
/// @link: https://ideone.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://arxiv.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; /// not likely to happen more
}
}
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;
}
/// you can modify to -> Bignum / Modulo / Overflow
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://math.stackexchange.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)
{
ll cbT = cbrt(T); /// Not very accuracy
while (cbT * cbT * cbT < T) ++cbT;
while (cbT * cbT * cbT > T) --cbT;
/// [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;
}
there is no time limit so brute-force is enough
The bonus problem itself doesnt have the constraint, so I fixed my blog that 1 second time limit and 1Gb memory limit and non-negative tuple
You should specify constraints for $$$a, b, c$$$ as well. For example, for any $$$x$$$ there is a solution $$$a = 0, b = x, c = -x$$$, since for those $$$0 \leq a + b + c = 0 + x - x = 0 \leq S$$$ and $$$0 \leq a \cdot b \cdot c = 0 \leq T$$$ and for every $$$S$$$ and $$$T$$$ the answer is infinity.
When you include constraints for $$$a, b, c$$$ as $$$ 0 \leq a, b, c$$$, then constraints $$$0 \leq a + b + c$$$ and $$$0 \leq a \cdot b \cdot c$$$ become redundant ;)
Ah yes, I just also fix that too, at exact the time you submit your comment, sorry about that
I have a question too, how many pairs (x, y) such that x, y >= 0 satisfy following condition: x + y <= S, x * y <= T
(When I was trying these post's problem, I encountered this and I just wonder, thanks.)
AFAIK this problem can be solved in $$$O(\sqrt[3]{T})$$$
I think i might have something. WLOG assume x<=y<=z. Note x<=10^6. Iterate for x. After that note that if product is fixed, sum of two numbers is minimal when they are as close to each other as possible. So you can use binary search for rest i think.
That is a good approach, which I think it will be the real solution
But I still find it very difficult to get the quick answer for fixed $$$k$$$ in $$$O(1)$$$ or $$$O(polylog(S) + polylog(T))$$$
Subproblem: Count such pair $$$(x, y)$$$ satisfy $$$(x + y \leq S - k)$$$ and $$$(x \times y \leq \frac{S}{k})$$$ and $$$(x \geq y \geq k)$$$
Honestly, I don't think any "good" solution exists
Let's say you want want to solve this problem for just two numbers(brute force the smallest one up to 10^6)
Now for fixed values of $$$S, T$$$ you want to find the number of pairs $$$(a, b)$$$, such that $$$a+b \leq S$$$ and $$$ab \leq T$$$
It's not hard to see that for a fixed value of $$$a$$$, the number of "good" $$$b$$$ is $$$min(\lfloor \frac{T}{a} \rfloor, S - a)$$$
And now you want to know the sum of this expression for all $$$a \leq S$$$, but if you take a look at the graphs of $$$S - a$$$ and $$$\frac{T}{a}$$$, you'll notice that in general case almost for all $$$a$$$ the graph of a fraction will lie below the graph of a line, thus solving this problem becomes close to finding smth similar to $$$\sum_{a=1}^{S}{\lfloor \frac{T}{a} \rfloor}$$$, and the best time complexity(AFAIK) for it is $$$O(\sqrt{T})$$$, which is too large.
I am wondering if I can use pollard rho by some ways to reduce its complexity or a magic math trick that I never know about to calculate quick too. Yet my best this far only $$$O(\sqrt{T})$$$ to calculate that part
There's a profoundly beautiful algorithm for computing $$$\sum_{a=1}^{S} \lfloor \frac{T}{a} \rfloor$$$ in $$$\tilde{O}(T^{1/3})$$$ time (in practice) which this margin is too small to contain.
PS: https://www.spoj.com/problems/DIVCNT1/ (It's not the one in the linked paper.)
Can you please share some paper/blog where I can read about this other algorithm?
I do have some
This solution with full explanation
This paper with approximate algorithm
Thanks!
i think the sample cases are wrong. for example input:
10 10 should give 193
edit: i was wrong it should be 213.
edit2: is there any solution faster than O(s^2)?
Yes there is, currently I am achieving $$$O(S log S + sqrt(T))$$$ but a little bug to optimize to $$$O(S log S + sqrt(sqrt(T)))$$$
Please share the O(s^2) approach.
Spending for 3 days and I cant optimize more, so I decide to quit.
The best I achieve for this problem (which I used to generate the test cases above) is $$$O(S \times T^{\frac{1}{3}})$$$ (use for large T small S) and $$$O(T^{\frac{5}{6}})$$$ (use for large S small T) (both can calculate $$$S = T = 10^{10}$$$ under 1 second)
Good luck to anyone who try to solve this with a better algorithm <3
Update: Now it is $$$O(T^{\frac{2}{3}})$$$ and calculate $$$S \leq 10^{18}$$$ and $$$T \leq 10^{12}$$$ in $$$830ms$$$
Update: Using integral, my real complexity is actually only $$$O\Huge(\normalsize \overset{min(S, \lfloor \sqrt[3]{T} \rfloor)}{\underset{a = 1}{\Huge \Sigma}} \LARGE( \normalsize log_2(\Large \lfloor \normalsize \sqrt{\frac{T}{a}} \Large \rfloor) \LARGE + \Large \lfloor \normalsize \normalsize \frac{T}{a} \Large \rfloor \LARGE ^{^{\normalsize 1/3}}) \Huge) \normalsize = O\Large( \int_{_{\normalsize 1}}^{^{\normalsize T^{1/3}}}\frac{\normalsize T^{1/3}}{\normalsize a^{1/3}} \normalsize da \Large) \normalsize = O(T^{5/9})$$$
No papers were found to has a better bound
Amazing Problem! BTW, I reckon that you're supposed to mention a,b,c are non-negative intergers.
$$$min(a, b, c) \geq 0$$$ condition is mentioned :(
e, I mean, integer
Oh, ok, gonna fix that later. (Though I actually tried to count real numbers too)