Long Overflow

help
1

https://www.codechef.com/viewsolution/939180

In the above solution

            if (d1 > K/d2)
		std::cout << "1" << std::endl;
	else
	{
		uint64_t ans = (K / (d1 * d2));

		ans <<= 1;
		ans |= 1;

		std::cout << ans << std::endl;
	}

this whole thing could havee been easily written as
2 * (k / (d1*d2)) + 1

But while trying this way answer is coming to be wrong.
Can someone tell me why ?

2

Consider the testcase:

1                  
10000000000 10000000000 1844674409 1844674409 10000000000000

Edit:

Slightly tighter:

1
10000000000 10000000000 1844674409 1844674409 16290448385

Generated via:

#include <iostream>
#include <cassert>
#include <limits>

using namespace::std;

uint64_t gcd(uint64_t x, uint64_t y)
{
	return ((x % y) == 0 ? y : gcd(y, x % y));
}

int main(int argc, char* argv[])
{
    uint64_t MAX = 1; // 10^18, from the Problem constraints.
    for (int i = 0; i < 18; i++)
    {
        MAX *= 10;
    }
    cout << 1 << endl;
    // Choose A and B so that gcd(A, B) = A.  A is mostly arbitrary.
    const uint64_t A = 10'000'000'000ULL;
    const uint64_t B = A;
    // Choose C so that:
    //   i) gcd(A, B) (= A) is co-prime to C (i.e. so that d - note the capitalisation! = 1);
    //  ii) gcd(A, B) (= A) * gcd(C, D) (= C) overflows a uint64_t and ends up fairly "small" - 
    //      <= 10^18, at least!
    uint64_t C = std::numeric_limits<uint64_t>::max() / A + 1;
    while (gcd(A, C) != 1)
    {
        C++;
    }
    const uint64_t D = C;
    // (A * C) overflows a uint64_t - set K to this number, +1.
    const uint64_t K = A * C + 1;
    // Check we haven't exceeded the constraints.
    assert(1 <= A && A <= MAX);
    assert(1 <= B && B <= MAX);
    assert(1 <= C && C <= MAX);
    assert(1 <= D && D <= MAX);
    assert(1 <= K && K <= MAX);
    cout << A << " " << B << " " << C << " " << D << " " << K << endl;
    return 0;
}
4 Likes
3

Thanks @ssjgz for the detailed explaination, really appreciate your effort.

One last doubt, since d1 * d2 can exceed the limit of the long, how is (d1 > k/d2) stopping that to happen in the if block ?
Because in the else block, we are doing (k / (d1*d2)), which means we are certain that here (d1 * d2) won’t exceed the long limit.

1 Like
4

If we’re in the else block, then d_1 \le \frac{K}{d_2} i.e. d_1 \times d_2 \le K (approximately) , so d_1 \times d_2 won’t overflow.

1 Like