 # Long Overflow

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 ?

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

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

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