笔试时间：2025年03月31日

历史笔试传送门：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题

题目：

小红有一个正整数 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 ≤ 10001 ≤ n, k ≤ 10⁹

输出描述

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

样例输入

2

6 2

6 10

样例输出

5

14

参考题解

因子预计算遍历1到√n找出所有因子对（i和n/i）排序因子列表为后续二分查找做准备动态边界二分查找初始左边界设为k（第k个非因子至少≥k）右边界从k+因子数开始，动态倍增扩展直到覆盖解精准定位目标值在最终确定的范围内进行二分搜索通过upper_bound快速计算<=mid的因子数用mid - 因子数判断是否达到k个非因子。

C++：[此代码未进行大量数据的测试，仅供参考]

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

using namespace std;

// Function to get all factors and sort them
vector<long long> getFactors(long long n) {
    vector<long long> factors;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            factors.push_back(i);
            if (i != n / i) {
                factors.push_back(n / i);
            }
        }
    }
    sort(factors.begin(), factors.end());
    return factors;
}

// Custom upper_bound function
int upperBound(const vector<long long>& list, long long target) {
    int left = 0, right = list.size();
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (list[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

// Function to find the kth non-factor
long long findKthNonFactor(long long n, long long k, const vector<long long>& factors) {
    long long left = k;
    long long right = k + factors.size();
    
    // Dynamically extend the right boundary
    while (true) {
        long long mid = right;
        int cnt = upperBound(factors, mid);
        if (mid - cnt >= k) break;
        right *= 2;
    }

    // Binary search
    long long ans = 0;
    while (left <= right) {
        long long mid = left + (right - left) / 2;
        int cnt = upperBound(factors, mid);
        if (mid - cnt >= k) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return ans;
}

int main() {
    int t;
    cin >> t;
    while (t-- > 0) {
        long long n, k;
        cin >> n >> k;
        vector<long long> factors = getFactors(n);
        cout << findKthNonFactor(n, k, factors) << endl;
    }
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;


public class Main {
    // 获取所有因子并排序
    static List<Long> getFactors(long n) {
        List<Long> factors = new ArrayList<>();
        for (long i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                factors.add(i);
                if (i != n / i) {
                    factors.add(n / i);
                }
            }
        }
        Collections.sort(factors);
        return factors;
    }


    // 自定义upper_bound
    static int upperBound(List<Long> list, long target) {
        int left = 0, right = list.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }


    // 查找第k个非因子
    static long findKthNonFactor(long n, long k, List<Long> factors) {
        long left = k;
        long right = k + factors.size();
        
        // 动态扩展右边界
        while (true) {
            long mid = right;
            int cnt = upperBound(factors, mid);
            if (mid - cnt >= k) break;
            right *= 2;
        }


        // 二分查找
        long ans = 0;
        while (left <= right) {
            long mid = left + (right - left) / 2;
            int cnt = upperBound(factors, mid);
            if (mid - cnt >= k) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            long n = sc.nextLong();
            long k = sc.nextLong();
            List<Long> factors = getFactors(n);
            System.out.println(findKthNonFactor(n, k, factors));
        }
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

def get_factors(n):
    factors = []
    for i in range(1, int(n**0.5) + 1):