筆試時間：2025年03月31日

歷史筆試傳送門：

2023春招秋招筆試合集

2024春招秋招筆試合集

第一題

題目：

小紅有一個正整數(shù) n，她想找出第 k 個不是 n 的因子的正整數(shù)。例如，當(dāng) n = 6 時：6 的因子有：1, 2, 3, 6，不是 6 的因子的數(shù)依次為：4, 5, 7, 8, 9, 10, ……。如果 k = 2，答案就是 5（第二個不是 6 的因子的數(shù)）。

輸入描述

第一行輸入一個整數(shù) t，表示測試用例數(shù)。

接下來 t 行，每行包含兩個整數(shù) n 和 k。

1 ≤ t ≤ 10001 ≤ n, k ≤ 10?

輸出描述

對于每個測試用例，輸出一個整數(shù)，表示第 k 個不是 n 的因子的正整數(shù)。

樣例輸入

2

6 2

6 10

樣例輸出

5

14

參考題解

因子預(yù)計算遍歷1到√n找出所有因子對（i和n/i）排序因子列表為后續(xù)二分查找做準(zhǔn)備動態(tài)邊界二分查找初始左邊界設(shè)為k（第k個非因子至少≥k）右邊界從k+因子數(shù)開始，動態(tài)倍增擴展直到覆蓋解精準(zhǔn)定位目標(biāo)值在最終確定的范圍內(nèi)進(jìn)行二分搜索通過upper_bound快速計算<=mid的因子數(shù)用mid - 因子數(shù)判斷是否達(dá)到k個非因子。

C++：[此代碼未進(jìn)行大量數(shù)據(jù)的測試，僅供參考]

#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：[此代碼未進(jìn)行大量數(shù)據(jù)的測試，僅供參考]

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();
        
        // 動態(tài)擴展右邊界
        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：[此代碼未進(jìn)行大量數(shù)據(jù)的測試，僅供參考]

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