题意分析

1. 问题定义：
   • 给定$m$，求所有与$m$互质的正整数组成的升序序列中的第$K$项。
2. 关键性质：
   • 与$m$互质的数具有周期性，周期为$\phi(m)$（欧拉函数）。

解题思路

1. 欧拉函数预处理：
   • 计算$\phi(m)$，表示$[1,m]$中与$m$互质的数的个数。
2. 周期定位：
   • 第$K$个数可表示为：$K = q \times \phi(m) + r$
   • 在$[q \times m + 1, (q+1) \times m]$范围内寻找第$r$个互质数
3. 二分搜索：
   • 对候选数$x$，统计$[1,x]$中与$m$互质的数的数量
   • 使用容斥原理计算互质数数量

实现步骤

1. 分解质因数：
   • 对$m$进行质因数分解，得到所有素因子
2. 容斥计算：
   • 对于给定$x$，计算$[1,x]$中能被$m$的任一素因子整除的数的个数
   • 互质数数量 = $x$ - 被至少一个素因子整除的数的个数
3. 二分框架：
   • 在$[1, K \times m]$范围内二分查找满足条件的$x$
4. 结果验证：
   • 检查$x$是否确实是与$m$互质的第$K$个数

代码实现

#include<cstdio>
using namespace std;
typedef long long ll;

const int maxm = 1000005;

int gcd(int a, int b) {
    return 0 == b ? a : gcd(b, a%b);
}

int a[maxm];

int main() {
    int m, k;
    while (scanf("%d%d", &m, &k) == 2) {
        int cnt = 0;
        for (int i = 1; i <= m; ++i) {
            if (gcd(m, i) == 1) {
                a[cnt++] = i;
            }
        }
        ll ans = a[(k - 1) % cnt];//下标从0开始,k-1向前偏移一位
        ans += (ll)m*(ll)((k - 1) / cnt);
        printf("%lld\n", ans);
    }
    return 0;
}