Codeforces 1474B: Different Divisors

Codeforces 1474B C++ 一解.

分析

$a$ 至少要有 $4$ 个因子 (自然包括 $1$ 和 $a$ 本身), 且任意两因子的差不小于 $d$. 为使 $a$ 尽可能小, 我们只希望 $a$ 有且仅有 $4$ 个因子, 也就是再确定两个不同的质因子 $p,q$ ($a=pq$, 且不妨设 $p<q$).

一个很显然的事实是: 对于充分大的 $d$, 我们越能保证 $a-q\geq d$ (不会证明故从略), 因此我们只需要在质数表中找到不小于 $1+d$ ($1$ 即是因子升序排列的第一个因子) 的 $p$ (第二个因子) 和不小于 $p+d$ 的 $q$ (第三个因子), 再确保 $a$ (第四个因子) 与 $q$ 的差不小于 $d$ 即可. 经过验证, 对于 $d=1$ 依然有 $a-q\geq d$.

生成质数表

生成质数表的方式有很多. 以下代码中尝试利用 STL 的 vector<int> 动态生成/更新指定范围内的质数表. 当然考虑到 $d\leq 10,000$, 可以直接生成完整长度 (所需的最大质数为 $20,011$, 根据质数定理估计质数表长度为 $2020$) 的质数表.

代码

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

#define MAX_PRIME (20011) // 10007 and 20011 are primes.

using namespace std;

bool isPrime(int x)
{
    if (x == 1)
    {
        return false;
    }
    if (x == 2)
    {
        return true;
    }
    if (x % 2 == 0)
    {
        return false;
    }

    for (int i = 3; i <= int(floor(sqrt(x))); i += 2)
    {
        if (x % i == 0)
        {
            return false;
        }
    }

    return true;
}

vector<int> updatePrimes(int maxn, vector<int> primes)
{
    int lastPrime = 2;

    if (primes.size())
    {
        lastPrime = primes.back();
    }
    else
    {
        primes.push_back(2);
    }

    for (int i = lastPrime + (lastPrime == 2 ? 1 : 2); i <= maxn; i += 2)
    {
        if (isPrime(i))
        {
            primes.push_back(i);
        }
    }

    return primes;
}

vector<int> updatePrimes(int maxn)
{
    return updatePrimes(maxn, vector<int>());
}

int solve(int d, vector<int> primes)
{
    vector<int>::iterator index1 = lower_bound(primes.begin(), primes.end(), 1 + d);
    vector<int>::iterator index2 = lower_bound(primes.begin(), primes.end(), *index1 + d);

    return *index1 * *index2;
}

int main()
{
    int t, d;
    vector<int> primes = updatePrimes(MAX_PRIME);

    cin >> t;

    while (t--)
    {
        cin >> d;
        cout << solve(d, primes) << endl;
    }

    return 0;
}