统计分母在区间[a,b]的最简真分数共有多少个？并求这些最简真分数升序序列中的第k项。 所谓最简真分数是指：分子小于分母，且分子分母无公因数的分数

统计分母在区间[a,b]的最简真分数共有多少个？并求这些最简真分数升序序列中的第k项。

所谓最简真分数是指：分子小于分母，且分子分母无公因数的分数。

这个循环就可以了

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e4 + 5;
int phi[MAXN];
int prime[MAXN];
int cnt_prime = 0;

void get_phi(int n) {
    phi[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(phi[i] == 0) {
            phi[i] = i - 1;
            prime[cnt_prime++] = i;
        }
        for(int j = 0; j < cnt_prime && prime[j] * i <= n; j++) {
            if(i % prime[j] == 0) {
                phi[i*prime[j]] = phi[i] * prime[j];
                break;
            }
            else phi[i*prime[j]] = phi[i] * phi[prime[j]];
        }
    }
}

int main() {
    int a, b, k;
    cin >> a >> b >> k;
    get_phi(b);
    int idx = 0;
    vector<pair<int,int>> vec;
    for(int i = a+1; i <= b; i++) {
        if(i == 1) continue; // 分母不能为1
        int fz = phi[i];
        int fm = i;
        int g = __gcd(fz, fm);
        fz /= g;
        fm /= g;
        vec.push_back(make_pair(fz, fm));
    }

    sort(vec.begin(), vec.end());
    vec.erase(unique(vec.begin(), vec.end()), vec.end());

    if(k > vec.size()) cout << "NO\n";
    else cout << vec[k-1].first << '/' << vec[k-1].second << endl;

    return 0;
}

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7626925
• 除此之外, 这篇博客: 结构体的内存对齐&共用体的大小端问题中的 我用开房的例子来讲解,加入a,b,c每个人住宿的时候对房间面积的最小要求是1平米,4平米,1平米.如果能保证这个空间大小,他们是愿意挤一个房间的,但是房间的大小规格是一样的,它总是刚好能满足需求最大的那个人,即每个房间4平米.注意分房间是必须是按照顺序来分,具体过程可以这么来理解: 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
  

  1,先开第一个房,让a住进去.
  2,因为b没有办法塞到第一个房间里,所以需要再开第二间房.
  3,由于b刚好住满第二间房,所以c只能再开一间房单独住.
  **所以最终需要开3间房,一共是12平米.有人会问,为什么a,c不去挤一间房呢.这么跟你解释,他们分配的顺序不连续,想挤在一起都没有机会.

  typedef struct Node
      {
          char    a;
          int     b;
          char    c;
      }Node;
      printf("%d", sizeof(Node));  //12

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^