Day7 完善程序完整程序组（重制版·15题）

共 3 个完整程序组。每组先说明程序功能、已有变量和输出要求，再选择各空应填内容。

第一组：一组整数的 gcd 与 lcm

---

程序功能

给定 $n$ 个正整数，程序依次读入这些数，计算它们的最大公约数与最小公倍数，并按“gcd lcm”的顺序输出。已保证最终最小公倍数不超过 long long 范围。变量 g 保存已读整数的最大公约数，l 保存已读整数的最小公倍数。试补全程序。

#include <iostream>
#include <numeric>
using namespace std;

int main() {
    int n;
    cin >> n;
    long long g = 0, l = 1;
    for (int i = ____①____; i <= ____②____; ++i) {
        long long x;
        cin >> x;
        g = gcd(____③____, x);
        l = l / ____④____ * x;
    }
    cout << ____⑤____ << " " << l;
    return 0;
}

第 1 题

①处应填（ {{ select(1) }} ）。

• 0
• 1
• 2
• n

---

第 2 题

②处应填（ {{ select(2) }} ）。

• n-1
• n
• 2*n
• x

---

第 3 题

③处应填（ {{ select(3) }} ）。

• 0
• 1
• g
• l

---

第 4 题

④处应填（ {{ select(4) }} ）。

• gcd(g,x)
• gcd(l,x)
• g*x
• l*x

---

第 5 题

⑤处应填（ {{ select(5) }} ）。

• n
• x
• g
• g+l

---

第二组：多次查询区间质数个数

---

程序功能

给定上界 $n$ 和查询次数 $q$。程序先用埃氏筛判断 $1\sim n$ 中的质数，再建立前缀计数数组 pre；每次输入 $1\le l\le r\le n$，输出闭区间 $[l,r]$ 内质数的个数。prime[i] 表示 $i$ 是否为质数，pre[i] 表示不超过 $i$ 的质数个数。试补全程序。

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    vector<bool> prime(n + 1, true);
    prime[0] = false;
    if (____①____) prime[1] = false;

    for (int i = 2; ____②____; ++i)
        if (prime[i])
            for (int j = ____③____; j <= n; ____④____)
                prime[j] = false;

    vector<int> pre(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        pre[i] = pre[i - 1] + prime[i];

    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << pre[r] - ____⑤____ << '\n';
    }
    return 0;
}

第 6 题

①处应填（ {{ select(6) }} ）。

• n>=1
• n==0
• q>=1
• prime[1]

---

第 7 题

②处应填（ {{ select(7) }} ）。

• i<=n
• i*i<=n
• i<n/2
• i%2==0

---

第 8 题

③处应填（ {{ select(8) }} ）。

• 2
• i
• 2*i
• i*i

---

第 9 题

④处应填（ {{ select(9) }} ）。

• ++j
• j*=i
• j+=i
• j+=2

---

第 10 题

⑤处应填（ {{ select(10) }} ）。

• pre[l]
• pre[l-1]
• prime[l]
• pre[r-1]

---

第三组：网格路径计数

---

程序功能

在一个 $h\times w$ 的方格点阵中，从左上角走到右下角，每一步只能向右或向下。程序使用 Pascal 递推计算不同路径条数，并对 $10^9+7$ 取模。总步数为 $h+w-2$，其中向下需要 $h-1$ 步，因此答案为组合数 $C_{h+w-2}^{h-1}$。试补全程序。

#include <iostream>
using namespace std;

const long long MOD = 1000000007;
long long c[205][205];

int main() {
    int h, w;
    cin >> h >> w;
    int n = h + w - 2;
    c[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        c[i][0] = c[i][i] = ____①____;
        for (int j = 1; ____②____; ++j)
            c[i][j] = (____③____ + c[i - 1][j]) % MOD;
    }
    cout << c[____④____][____⑤____];
    return 0;
}

第 11 题

①处应填（ {{ select(11) }} ）。

• 0
• 1
• i
• MOD

---

第 12 题

②处应填（ {{ select(12) }} ）。

• j<=i
• j<i
• j<n
• j*j<=i

---

第 13 题

③处应填（ {{ select(13) }} ）。

• c[i][j-1]
• c[i-1][j-1]
• c[i+1][j-1]
• c[i-1][j+1]

---

第 14 题

④处应填（ {{ select(14) }} ）。

• h
• w
• n
• h*w

---

第 15 题

⑤处应填（ {{ select(15) }} ）。

• h-1
• w
• n-1
• h+w

---