题解

本题要求找出第 k 个不是 n 的因子的正整数。给定正整数 n，其因子满足一定的规律。我们可以先求出 n 的所有因子，然后利用因子之间的间隔计算出哪些区间内的数字为非因子。具体来说，对于任意一个正整数 x，如果在区间 [1, x] 中 n 的因子个数为 i，那么区间内非因子个数为 x - i。当 x - i 大于等于 k 时，说明第 k 个非因子出现在区间 [1, x] 内，可以直接通过数学关系求出答案。

本题代码采用如下思路：

1. 求 n 的因子
   遍历 1 至 √n，若 x 为 n 的因子，则将 x 和 n//x 加入因子列表（注意去重），最后对因子列表进行排序。

2. 利用因子间隔确定答案
   用变量 i 表示遍历到当前的因子数量，对于每个因子 f，区间 [1, f] 内非因子个数为 f - i。如果 f - i ≥ k，则说明第 k 个非因子在 f 之前，可以通过 i+k-1 得到答案；否则继续遍历所有因子。当所有因子遍历完后，说明答案落在 n 之后，此时直接返回 i+k。

3. 时间复杂度
   求因子集合的时间复杂度为 O(√n)，排序因子列表的时间复杂度较低（因子个数最多在 10^5 左右，实际远小于 n），整体时间复杂度可以接受。

Python 代码

# 读入测试用例个数
T = int(input())
while T > 0:
    T -= 1
    n, k = map(int, input().split())
    
    # 求 n 的因子列表
    fs = []
    x = 1
    while x * x <= n:
        if n % x == 0:
            fs.append(x)  # x 是因子
            if x != n // x:
                fs.append(n // x)  # 加入 n/x
        x += 1
    # 将因子排序
    fs.sort()
    
    # i 表示已经遍历的因子个数
    i = 0
    flag = False
    for f in fs:
        i += 1
        # 区间 [1, f] 内非因子个数为 f - i
        if f - i >= k:
            # 第 k 个非因子就是 i + k - 1
            print(i + k - 1)
            flag = True
            break
    # 如果在因子区间内没有找到答案，则答案在 n 后面（n 后面的数字都不是 n 的因子）
    if not flag:
        print(i + k)

JAVA 代码

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 读入测试用例个数
        int T = sc.nextInt();
        while(T-- > 0) {
            int n = sc.nextInt();
            long k = sc.nextLong();
            
            // 求 n 的因子列表，使用 ArrayList 存储
            ArrayList<Integer> factors = new ArrayList<>();
            for (int x = 1; x * x <= n; x++) {
                if(n % x == 0) {
                    factors.add(x);
                    if(x != n / x) {
                        factors.add(n / x);
                    }
                }
            }
            // 对因子列表排序
            Collections.sort(factors);
            
            int i = 0;  // 已遍历的因子个数
            boolean found = false;
            for (int f : factors) {
                i++;
                // 区间 [1, f] 内非因子数为 f - i
                if (f - i >= k) {
                    // 第 k 个非因子数为 i + k - 1
                    System.out.println(i + k - 1);
                    found = true;
                    break;
                }
            }
            // 如果在因子区间内没有找到答案，则答案在 n 后面
            if (!found) {
                System.out.println(i + k);
            }
        }
        sc.close();
    }
}

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while(T--){
        int n;
        long long k;
        cin >> n >> k;
        
        // 求 n 的因子列表
        vector<int> factors;
        for (int x = 1; x * x <= n; x++){
            if(n % x == 0){
                factors.push_back(x);
                if(x != n / x){
                    factors.push_back(n / x);
                }
            }
        }
        // 对因子列表排序
        sort(factors.begin(), factors.end());
        
        int i = 0;  // 计数已遍历的因子个数
        bool found = false;
        for (int f : factors) {
            i++;
            // 区间 [1, f] 内非因子数为 f - i
            if(f - i >= k) {
                // 第 k 个非因子数为 i + k - 1
                cout << i + k - 1 << "\n";
                found = true;
                break;
            }
        }
        // 如果在因子区间内没有找到答案，则答案在 n 后面
        if(!found) {
            cout << i + k << "\n";
        }
    }
    return 0;
}

题目内容

小红有一个正整数$n$，她想找出第$k$个不是$n$的因子的正整数。

例如，当$n=6$时：$6$的因子有：$1,2,3,6$,不是$6$的因子数依次为：$4,5,7,8,9,10,......$。如果$k=2$，答案就是$5$（第二个不是$6$的因子的数）

输入描述

第一行输入一个整数$t$,表示测试用例数。

接下来$t$行，每行包含两个整数$n$和$k$。

$1≤t≤1000$

1≤n,k≤10^9

输出描述

对于每个测试用例，输出一个整数，表示第$k$个不是$n$的因子的正整数。

样例1

输入

2
6 2
6 10

输出

5
14