Well, first of all it's obvious that gcd(a, b) = gcd(b, a - b), so a pair of numbers (a, b) is good if and only if after we do steps from the kgcd procedure, we reach a pair of numbers (a', b') with a' > 0, b' ≤ 0 such that a' + b' = gcd(a', b'). Now obviously gcd(a', b')|a' + b' so we need only to find pairs of numbers (a', b') such that a' + b'|a' and a' + b'|b', because it's equivalent to a' + b'|gcd(a', b'). But a' + b'|a' ≡ a' + b'|a' - (a' + b') ≡ a' + b'|b'. So the only condition we need is that a' + b' = d, where d is some positive divisor of a', so the good "ending" pairs are of the form (a', d - a') = (k * d, d - k * d), where a' = k * d.

Now, a crucial observation is that using the kgcd procedure, the pair of numbers form long "linear" chains that do not intersect (a, b) -  > (b, a - b) -  > (a - b, 2b - a) -  > ... -  > (x, y), that's because we can reach pair (x, y) only from (x + y, x) directly. So we can partition pairs of numbers in equivalence classes by their "ending" pairs, that is the pair (x, y) with x > 0, y ≤ 0. Now by the above obsevation, we are only interested in pairs of the form (k * d, d - k * d) for some d and k. If we look at the chain that starts from these kind of pairs and go backwards, then they look something like this (k * d, d - k * d)

 <  - (d, k * d) <  - (d + k * d, d) <  - (2d + k * d, d + k * d)

 <  - (3d + 2k * d, 2 * d + k * d)  <  - (5 * d + 3k * d, 3d + 2k * d) <  - ...

Now, to make the explanation shorter, each pair is of the form (F_n * k * d + F_n + 1 * d, F_n - 1 * k * d + F_n * d) so if we fix n, k, d we've got ourselves a pair. Now for a fixed n we need to find all k, d with F_n * k * d + F_n + 1 * d ≤ N (it's enough, because the second number will always be less, except the first pair (d, k * d) which we count separately). So if we range d from 1 to N, we get that we need to find which can be done in O(sqrt(N)) using an well known technique. In the end the total complexity of O(logN * sqrtN) per test because fibonacci numbers grow exponentially(I think).

The code is really short: http://ideone.com/flvne6

Editorial for KGCD should be available on the website.

This is pretty much what the testers solution (i.e. my solution) does. The setter (RomaWhite) however had a quite different solution that did not use generating functions, and instead relied on inclusion-exclusion to find the answer. You may refer to the editorial to see that solution described.

Ah, I didn't really have much time to look at the actual scores on the original 50 test cases. Locally I tried to minimize the sum of (diff1/1 + diff2/2 + ...) and didn't really compute actual scores according to the scoring formula. Anyway, this is another point in favour of not having some parameters range too much across tests (in this case the K parameter), because the class of tests with large K was very small, and luck (or bad luck) on these test cases can influence the final result a lot.

What I liked about the problem was that it wasn't "easy". Up to the end of the contest I could still come up with improvements and I'm sure I was very far from anything close to optimal. In fact, an interesting thing about the problem is that given more time, my solution would be able to keep producing better scores on most of the test cases. I believe this is also true for your solution — I saw the "relax" function, which is quite similar to mine. Given more time, it would have probably "relaxed" the values much more, thus improving the final score.

Two of my most recent submissions from the contest have been in "Rejudge" mode for many hours (the last one and the 3rd most recent one). What is going on? At this point it will probably not make too much of a difference in the rankings (I think that my best submission was already rejudged), but it's worrying to know that some of the submissions will randomly not be rejudged on the final test cases.

PS: I posted the same comment on the problem page, but maybe there's a higher chance of getting an answer here.