按分母和分子的升序查找两个给定分数之间的不可约分数

Question

Time limit per test: 2 seconds
Memory limit per test: 512 megabytes

You are given two fractions a/b < c/d and a positive number N. Consider all irreducible fractions e/f such that 0 < e, f ≤ N and a/b < e/f < c/d. Let s be a sequence of these fractions sorted in ascending order of denominators and then numerators (fraction e1/f1 precedes e2/f2 if either f1 < f2 or f1 = f2 and e1 < e2). You should print first n terms of the sequence s or the whole sequence s if it consists of fewer than n terms.

Input
The first line of each test contains 6 integers a, b, c, d, N, n (0 ≤ a ≤ 10^18, 1 ≤ b, c, d, N ≤ 10^18, 1 ≤ n ≤ 200 000, a/b < c/d).

Output
First, print how many terms of sequence s you will output. And then output these terms in the right order.

Examples
Input:
0 1 1 1 5 10
Output:
9
1 2
1 3
2 3
1 4
3 4
1 5
2 5
3 5
4 5
Input:
55 34 68 42 90 1
Output:
1
89 55
Input:
49 33 45 30 50 239
Output:
0

到目前为止，我只设法编写了一个解决方案，它迭代了从 1 到 N 的所有分母，并且对于每个分母迭代了从 a*f/b 的所有分子] 到 c*f/d，将所有找到的不可约分数添加到答案中。

这是我的代码：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

long long a, b, c, d, N, n;
vector<pair<long long, long long>> result;

long long gcd(long long a, long long b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

void computeResult() {
    for (long long f = 1; f <= N; f++) {
        long long eMax = c*f / d;
        if (c*f % d != 0) eMax++;
        eMax = min(eMax, N);
        for (long long e = a*f / b + 1; e < eMax; e++) {
            if (gcd(e, f) == 1) {
                result.push_back(make_pair(e, f));
                if (result.size() == n)
                    return;
            }
        }
    }
}

int main() {
    cin >> a >> b >> c >> d >> N >> n;  
    computeResult();
    cout << result.size() << endl;
    for (pair<long long, long long> fraction : result)
        cout << fraction.first << " " << fraction.second << endl;
}

不幸的是，这个解决方案太慢了。我想知道如何更有效地解决这个问题。

Answer 1

您应该遍历从 1 到 N 的所有分母，但您不需要遍历给定范围内的所有分子。

对于任何不可约分数numerator/denominator，分子和分母是coprimes。因此，您需要的是有效地生成 denominator 的所有互素，其中 co-prime/denominator 位于给定范围内。

例如，对于分母 = 8，互质数为 1,3,5,7。 [0,1] 范围内的不可约分数为 1/8、3/8、5/8、7/8。您可以通过向它们添加一个整数来扩展不可约分数的范围：1+1/8、1+3/8、1+5/8、1+7/8 => 9/8、11/8、13/ 8, 15/8 是 [0+1,1+1] = > [1,2]

范围内以 8 为分母的不可约分数

用于生成 x 的所有互素数的伪代码，使得 a/b < coprime/x < c/d :

prime_factors_of_x = get_prime_factors(x)
is_coprime = boolean array of size x
set every element of is_coprime to True
// next, set to False all elements indexed by multiples of a prime factor of x
for every factor in prime_factors_of_x:
   // next loop can be a vectorial operation in some languages
   for i in 0..(x/factor):
      is_coprime[i*factor] = False

all_coprime_list = [] // empty list
min_coprime = floor(a/b * x)+1
max_coprime = floor(c/d * x)-1
for i in min_coprime..max_coprime:
   if is_coprime[i mod x]:
      all_coprimes_list.append(i)

这是总体思路。

Answer 2

这是一个非常有趣的问题，我真的很喜欢思考它，我不知道为什么它会收到这么多反对票。无论如何，下面是我的解决方案粗略草图。如果我对它进行一些改进，我会在稍后更新我的答案。

正如 , we need a more effective way to generate coprimes. A common technique (that is used in diophantine equation solvers) is Farey Sequence 所建议的那样。

Definition: a Farey Sequence of order n between a/b and c/d is the ascending (by value) sequence of irreducible fractions p/q such that a/b <= p/q <= c/d, where q < n.

Farey 序列的属性在 this paper 中介绍。所以，我们手头有几个问题：

如何有效生成阶n的Farey序列?
知道第一个元素a0/b0 = a/b和第二个元素a1/b1，可以使用以下算法生成a2/b2（复杂度O(1)）：
```
k = int((n + b0) / b1)
a2 = k * a1 - a0
b2 = k * b1 - b0
```
如何获取n阶Farey序列的第二个元素?
我们知道分母在 1..n 范围内的某处。我们还知道 a/b 和 c/d 是 Farey 序列中的邻居当且仅当 b*c - a*d = 1 时。因此，通过迭代 d 到 1..n 的值，我们可以找到最小的分数，这将是序列中的下一个分数。复杂度 O(n).
我们如何决定我们应该生成哪个顺序的 Farey 序列？
当 N 的数量级为 10^18 时，盲目生成订单 N 是愚蠢的。此外，您将没有足够的内存。我们只需要生成一个 k 阶的 Farey 序列，使其长度大于 200000 的 n 。这是这个算法最难的部分，现在数论中的工具只能让我们估计：|F_k| = 3*k^2 / pi^2。所以我们有：
```
k = ceil(sqrt(n * pi^2)) + C
```
在page 11 of this paper中你也可以找到这个公式的近似误差，让你容纳更多的误差空间，所以C。请注意，对于每个 a/b 和 c/d，F_k 的长度将不同。

综上所述，该算法的伪代码为：

1. Estimate the order k of the Farey Sequence to generate, such that |F_k| >= n
2. Calculate the second element of F_k. O(k), where k << n and 1 < n < 200000
3. Generate the whole Farey Sequence. O(n), where 1 < n < 200000
4. Sort by the requirements. O(n log n), where 1 < n < 200000

在最坏的情况下，当您在 step 1 中的估计给出的元素少于 n 时，您将需要使用更高阶 k' 再次生成。这只会将算法的执行时间增加一个常数。因此，总体复杂度平均为 O(n log n)，其中 n < 200000.

备注：该算法的瓶颈在于阶数估计k。这可以通过不使用 Farey 序列而完全避免 Stern-Brocot Tree。树完全按照您需要的顺序生成，但我怀疑在 a/b != 0/1 和 c/d != 1/1 的任意设置中它会以良好的顺序遍历所有分数。

Answer 3

除了其他问题，您会注意到如果 N=10^9 排序有效，但如果 N=10^18 则您的代码在乘以 f 时会溢出，一切都会崩溃。你可以做到 long long eMax = (long long)(((long double)c) * f / d); （对于下限也是类似的）来减少这个问题，但它会减慢它的速度。

按分母和分子的升序查找两个给定分数之间的不可约分数

Finding irreducible fractions between two given fractions in ascending order of denominators and then numerators

c++

algorithm

optimization

performance

fractions