通过在数组的第一个、最中间和最后一个这3个数据中选择中间值作为枢轴（比较基准），快速排序算法可降低落入最坏情况的概率。

相等序列

时间限制： 1.0 s

内存限制：512.0 MB

题目描述

小 A 有一个包含 N 个正整数的序列A = {A1 , A2 , · ·  ,AN} 。小 A 每次可以花费 1 个金币执行以下任意一种操作：

 选择序列中一个正整数 Ai （ 1 ≤ i ≤ N） ，将 Ai 变为 Ai * P ，P 为任意质数；

 选择序列中一个正整数 Ai （ 1 ≤ i ≤ N） ，将 Ai 变为 Ai /P ，P 为任意质数，要求Ai能被p整除。

小 A 想请你帮他计算出令序列中所有整数都相同 ，最少需要花费多少金币。

输入格式

第一行一个正整数N ，含义如题面所⽰ 。

第二行包含 N 个正整数 A1 , A2 , ·  … ,AN ，代表序列 A。

输出格式

输出一行 ，代表最少需要花费的金币数量。

输入样例

5
10  6  35  105  42

输出样例

8

数据范围

对于60%的测试点 ，保证 1 ≤ N, Ai ≤ 100 。

对于所有测试点 ，保证 1 ≤ N, Ai ≤ 105 。

小杨要把一根长度为 L 的木头切成 K 段，使得每段长度小于等于 x 。已知每切一刀只能把一段木头分成两段，他用二分法找到满足条件的最小 x （ x 为正整数），则横线处应填写（ ）。

// 判断：在不超过 K 次切割内，是否能让每段长度 <= x 
bool check(int L, int K, int x) { 
    int cuts = (L - 1) / x; 
    return cuts <= K; 
} 
// 二分查找最小可行的 x 
int binary_cut(int L, int K) { 
    int l = 1, r = L; 
    while (l < r) { 
        int mid = l + (r - l) / 2; 
        ________________________________ // 在此处填入代码 
    } 
    return l; 
} 
int main() { 
    int L = 10; // 木头长度 
    int K = 2; // 最多切 K 刀 
    cout << binary_cut(L, K) << endl; 
    return 0; 
}

if (check(L, K, mid)) 
    r = mid; 
else 
    l = mid + 1;

if (check(L, K, mid)) 
    r = mid+1; 
else 
    l = mid + 1;

if (check(L, K, mid)) 
    r = mid + 1; 
else 
    l = mid - 1;

if (check(L, K, mid)) 
    r = mid + 1; 
else 
    l = mid;

下述代码实现素数表的线性筛法，筛选出所有小于等于 的素数，则横线上应填的代码是( )。

vector<int> linear_sieve(int n) { 
    vector<bool> is_prime(n +1, true); 
    vector<int> primes; 
    is_prime[0] = is_prime[1] = 0; //0和1两个数特殊处理 
    for (int i = 2; i <= n; ++i) { 
        if (is_prime[i]) { 
            primes.push_back(i); 
    } 
    ________________________________ { // 在此处填入代码 
        is_prime[ i * primes[j] ] = 0; 
        if (i % primes[j] == 0) 
            break; 
        } 
    } 
    return primes; 
}

for (int j = 0; j < primes.size() && i * primes[j] <= n; j++)

for(int j = sqrt(n); j <= n && i * primes[j] <= n; j++)

for (int j = 1; j <= sqrt(n); j++)

for(int j = 1; j < n && i * primes[j] <= n; j++)

下面给出了阶乘计算的两种方式。以下说法正确的是（ ）。

int factorial1(int n) { 
    if (n <= 1) return 1; 
    return n * factorial1(n - 1); 
} 
int factorial2(int n) { 
    int acc = 1; 
    while (n > 1) { 
        acc = n * acc; 
        n = n - 1; 
    } 
    return acc; 
}