-
Notifications
You must be signed in to change notification settings - Fork 0
/
day 59
59 lines (48 loc) · 1.58 KB
/
day 59
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
#include <cmath>
#include <iostream>
// return length of period or 0 for perfect squares
unsigned int getPeriodLength(unsigned int x)
{
// without any fractional part yet ...
unsigned int root = sqrt(x);
// exclude perfect squares (no period)
if (root * root == x)
return 0;
// the integer part of sqrt(x)
unsigned int a = root;
// let's use a variable numerator to store what we subtract
unsigned int numerator = 0; // initially zero, e.g. 4 will appear in second iteration of sqrt(23)
unsigned int denominator = 1; // initially one, e.g. 7 will appear in second iteration of sqrt(23)
// count how long it takes until the next period starts
unsigned int period = 0;
// terminate when we see the same triplet (a, numerator, denominator) a second time
// to me it wasn't obvious that this happens exactly when a == 2 * root
// but thanks to Wikipedia for that trick ...
while (a != 2 * root)
{
numerator = denominator * a - numerator;
// must be integer divisions !
denominator = (x - numerator * numerator) / denominator;
a = (root + numerator) / denominator;
period++;
}
return period;
}
int main()
{
unsigned int last;
std::cin >> last;
// count all odd periods
unsigned int numOdd = 0;
for (unsigned int i = 2; i <= last; i++) // 0 and 1 are perfect squares
{
unsigned int period = getPeriodLength(i);
// count number of odd lengths (if not a perfect square)
if (period % 2 == 1)
numOdd++;
// branchless: numOdd += period & 1;
}
// print result
std::cout << numOdd << std::endl;
return 0;
}