首页 > 搜索 > DFS搜索 > hdu 2432 Farey Sequence Again-DFS-[解题报告]C++
2014
01-26

hdu 2432 Farey Sequence Again-DFS-[解题报告]C++

Farey Sequence Again

问题描述 :

      The Farey sequence Fn for any positive integer n is the set of irreducible rational numbers a/b with 0<a<b<=n and (a, b) = 1 arranged in increasing order. Here (a, b) mean the greatest common divisor of a and b. For example:
            F2 = {1/2}
            F3 = {1/3, 1/2, 2/3}
      Given two positive integers N and K, with K less than N, you need to find out the K-th smallest element of the Farey sequence FN.

输入:

      The first line of input is the number of test case T, 1<=T<=1000. Then each test case contains two positive integers N and K. 1<=K<N<=10^9.

输出:

      The first line of input is the number of test case T, 1<=T<=1000. Then each test case contains two positive integers N and K. 1<=K<N<=10^9.

样例输入:

3
2 1
100 68
101 69

样例输出:

1/2
2/83
1/42

这题本来完全没思路的,后来想一想,要不打个表找找规律吧。于是打了个表,真找到规律了。。。

打表的代码如下:

int n;
void dfs(int x1, int y1, int x2, int y2) {
    if (y1 + y2 <= n) {
        dfs(x1, y1, x1 + x2, y1 + y2);
        printf("%d/%d\n", x1 + x2, y1 + y2);
        dfs(x1 + x2, y1 + y2, x2, y2);
    }
}
void print_farey(int n) {
    printf("0/1\n");
    dfs(0, 1, 1, 1);
    printf("1/1\n");
}

int main() {
    freopen("data.in", "r", stdin);
    while(scanf("%d", &n) == 1) {
        print_farey(n);
    }
    return 0;
}

我发现的规律是:

①这个数列中,最开始会有约n/2项是分子为1的(分母从n开始每项递减1,直到ceil(n/2.0)结束);

②接着会有约n/3项,一个分子为2的分数与一个分子为1分数交替出现,分子为2的数分母从n(若n%2!=0)或n-1(若n%2==0)开始每项递减2,直到floor(n/3.0 + 1/3.0) * 2 + 1结束,分子为1的数的分母从上次结束的下一个位置即floor(n/2.0 + 1/2.0)-1开始每项递减1直到ceil(n/3.0)结束;

③再然后还会有约n/3项,以3/a,2/b,3/c,1/d的形式交替出现,其中a从n(或n-1,或n-2,即第一个不被3整除的数)开始每项递减3直到floor(n/4.0 + 1/4.0) * 3 + 2结束,b从上次结束的下一个位置即floor(n/3.0 + 1/3.0) * 2 – 1开始每项递减2直到floor(n/4.0+1/4.0) * 2 + 1结束,c从a-1开始每项递减3直到直到floor(n/4.0 + 1/4.0) * 3 + 1结束,d从上次结束的下一个位置即floor(n/3.0+1/3.0)开始每项递减1直到floor(n/4.0+1/4.0)结束。

这些项加起来就有n/2+n/3+n/3>n项了,所以题目所需第k项一定在这些项里,按此规律即可出结果。

最后通过的代码如下:

 

/*
 * hdu2432/win.cpp
 * Created on: 2012-11-3
 * Author    : ben
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;

/**
 * 得到n阶法里数列分子为1的连续段(到分子出现2时截止)长度
 */
inline int getflen(int n) {
    int t = (int)ceil(n / 2.0);
    return n - t + 1;
}
/**
 * 得到n阶法里数列分子为2和1交替出现的连续段(到分子出现3
 * 时截止)的长度
 */
inline int getslen(int n) {
    int s1 = n % 2 == 0 ? (n - 1) : n;
    int t1 = (int)floor(n/3.0 + 1/3.0) * 2 + 1;
    int ans = (s1 - t1) / 2 + 1;
    int s2 = (int)floor(n / 2.0 + 1 / 2.0) - 1;
    int t2 = (int)ceil(n/3.0);
    ans += s2 - t2 + 1;
    return ans;
}
/**
 * 得到n阶法里数列分子为3,1,2交替出现的连续段(到分子出现4
 * 时截止)的长度
 */
inline int gettlen(int n) {
    int s1 = n;
    while(s1 % 3 == 0) {
        s1--;
    }
    int t1 = (int)floor(n/4.0 + 1/4.0) * 3 + 2;
    int s3 = s1 - 1;
    int t3 = (int)floor(n/4.0 + 1/4.0) * 3 + 1;
    int s2 = (int)floor(n/3.0 + 1/3.0) * 2 - 1;
    int t2 = (int)floor(n/4.0 + 1/4.0) * 2 + 1;
    int s4 = (int)ceil(n/3.0) - 1;
    int t4 = (int)ceil(n/4.0);
    int ans = 0;
    if(s1 % 3 == 1) {
        ans += 2;
        s1 -= 2;
        s3 -= 2;
        s4 -= 1;
    }
    ans += (s1 - t1) / 3 + 1;
    ans += (s3 - t3) / 3 + 1;
    ans += (s2 - t2) / 2 + 1;
    ans += s4 - t4 + 1;
    return ans;
}
inline void get_f(int n, int k, int &a, int &b) {
    a = 1;
    b = n - k + 1;
}
inline void get_s(int n, int k, int &a, int &b) {
    int s1 = n % 2 == 0 ? (n - 1) : n;
    int s2 = (int)floor(n / 2.0 + 1 / 2.0);
    if(k % 2 == 1) {
        a = 2;
        b = s1 - k + 1;
    }else {
        a = 1;
        b = s2 - k / 2;
    }
}
inline void get_t(int n, int k, int &a, int &b) {
    int s1 = n;
    while(s1 % 3 == 0) {
        s1--;
    }
    int s2 = (int)floor(n/3.0 + 1/3.0) * 2 - 1;
    int s3 = (s1 % 3 == 2) ? (s1 - 1) : (s1 - 2);
    int s4 = (int)ceil(n/3.0) - 1;
    if(k % 4 == 1) {
        a = 3;
        b = s1 - (k - 1) / 4 * 3;
    }else if(k % 4 == 3) {
        a = 3;
        b = s3 - (k - 3) / 4 * 3;
    }else if((k % 4 == 2) xor (s1 % 3 == 2)) {
        a = 1;
        if(k % 4 == 2) {
            b = s4 - (k - 2) / 4;
        }else {
            b = s4 - (k - 4) / 4;
        }
    }else {
        a = 2;
        if(k % 4 == 2) {
            b = s2 - (k - 2) / 4 * 2;
        }else {
            b = s2 - (k - 4) / 4 * 2;
        }
    }
}
/**
 * 调用函数get_farey(n, k)即得结果,结果的第一项为分子,
 * 第二项为分母。程序时间与空间复杂度均为O(1)
 */

pair<int, int> get_farey(int n, int k) {
    pair<int, int> ret;
    int fl = getflen(n);
    int sl = getslen(n);
    if(k <= fl) {
        get_f(n, k, ret.first, ret.second);
    }else if(k <= sl + fl) {
        get_s(n, k - fl, ret.first, ret.second);
    }else {
        get_t(n, k - fl - sl, ret.first, ret.second);
    }
    return ret;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
#endif
    int T, n, k;
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &k);
        pair<int, int> ans = get_farey(n, k);
        printf("%d/%d\n", ans.first, ans.second);
    }
    return 0;
}

解题转自:http://www.cnblogs.com/moonbay/archive/2012/11/05/2756045.html


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法