-
Notifications
You must be signed in to change notification settings - Fork 0
/
day 66
109 lines (95 loc) · 2.87 KB
/
day 66
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
// multiply two unsigned number where the result may exceed the largest native data type
template <typename T>
void multiply(T a, T b, T& result_high, T& result_low)
{
const T Shift = 4 * sizeof(a);
const T Mask = T(~0) >> Shift;
auto a_high = a >> Shift;
auto a_low = a & Mask;
auto b_high = b >> Shift;
auto b_low = b & Mask;
auto c_0 = a_low * b_low;
auto c_1a = a_high * b_low;
auto c_1b = a_low * b_high;
auto c_2 = a_high * b_high;
auto carry = ((c_0 >> Shift) + (c_1a & Mask) + (c_1b & Mask)) >> Shift;
result_high = c_2 + (c_1a >> Shift) + (c_1b >> Shift) + carry;
result_low = c_0 + (c_1a << Shift) + (c_1b << Shift);
}
// if a/b < c/d (and all numbers are positive)
// then a*d < c*b
bool isLess(unsigned long long a, unsigned long long b, unsigned long long c, unsigned long long d)
{
// GCC has 128-bit support:
//return (unsigned __int128)x1 * y2 < (unsigned __int128)y1 * x2;
unsigned long long r1_high, r1_low;
unsigned long long r2_high, r2_low;
multiply(a, d, r1_high, r1_low);
multiply(c, b, r2_high, r2_low);
// compare high bits
if (r1_high < r2_high)
return true;
if (r1_high > r2_high)
return false;
// compare low bits
return (r1_low < r2_low);
}
int main()
{
unsigned int tests = 1;
std::cin >> tests;
while (tests--)
{
unsigned int a = 3;
unsigned int b = 7;
unsigned long long limit = 1000000;
std::cin >> a >> b >> limit;
// generate all numbers in the Farey sequence using binary subdivision
// for each step decide whether the number was left or right of the desired fraction
// start with 0/1 and 1/1
unsigned long long leftN = 0;
unsigned long long leftD = 1;
unsigned long long rightN = 1;
unsigned long long rightD = 1;
while (leftD + rightD <= limit)
{
auto mediantN = leftN + rightN;
auto mediantD = leftD + rightD;
// if x1/y1 < x2/y2 (and all numbers are positive)
// then x1*y2 < x2*y1
if (isLess(mediantN, mediantD, a, b))
{
// adjust left border
leftN = mediantN;
leftD = mediantD;
}
else
{
// adjust right border
rightN = mediantN;
rightD = mediantD;
// did we "hit the spot" ?
if (rightN == a && rightD == b)
break;
}
}
// now the right border is the fraction we read from input
// and we only have to adjust the left border from here on
//while (leftD + rightD <= limit) // gets the job done, but still slow ...
//{
// leftN += rightN;
// leftD += rightD;
//}
// "instant" result
if (limit >= leftD + rightD)
{
auto difference = limit - (leftD + rightD);
auto repeat = 1 + difference / rightD;
leftN += repeat * rightN;
leftD += repeat * rightD;
}
std::cout << leftN << " " << leftD << std::endl;
}
return 0;
}