目录
- 前置知识
- 题目描述
- 题目解析
- 总结
前置知识
C++ 基础，循环结构，数组有关操作。
题目描述
#include<iostream>
using namespace std;
long long dp[1000001],a,n,p = 0;
int main()
{cin >> n;for(long long i = 1;i<=n;i++){cin >> a;p = max(p,a);for (long long j = 1;j*j <= a;j++){if (a%j == 0){dp[j]++;if (j!=a/j) dp[a/j]++;}}}for(long long i = 1;i<=n;i++){while(dp[p] < i) p--;cout << p<<endl;}return 0;
}
已知所有输入都是 10^6 以内的正整数.
判断题:
1.如果某次输入的 a 大于了 1000001,则程序可能会 RE;
2.程序第 3 行的 p 不需要赋初值(即把 p=0 改为 p).
3.已知此程序时间限制1s,输入在题目允许范围内,程序可能会超时;
4.如果输入 4 1 2 3 4 则 20 行循环执行前,dp[1]~dp[4]的值分别是();
A.4 2 1 1
B.1 1 2 4
C.2 1 4 1
D.1 2 4 1
5.如果输入 4 18 81 54 63 则 20 行循环执行前,p 的值是();
A.4
B.18
C.81
D.63
6.如果输入 4 18 81 54 63 则输出是();
A.81 27 9 9
B.9 9 9 9
C.9 9 27 81
D.81 81 81 81
题目解析
程序大意：先用 dp 数组对 n 个数的因数进行计数，然后不断调整 p（减一操作），使得 dp[p] >= 1~n 中的每一个元素，同时每次输出 p 的值。可以证明，最后 p 值一定是 n 个数的最大公因数。
1.对
因为 dp 数组的最大长度为 1000001，所以最大访问下标为 1000000，输入 a 大于 1000001 会导致数组越界，从而 RE。
2.对
在 C++ 中，全局变量（在所有函数之外的变量，拥有全局作用域）默认赋值为 0，所以加不加 “= 0” 是没有区别的。
3.对
该程序的时间复杂度为 O(n × sqrt n)，当输入为 10^6 时明显会超时（在输入都是 10^6 的情况下，10^6 × sqrt(10^6) = 10^9，计算机每秒最多运行 10^7 条程序，会超时）。
4.A
在 20 行循环前，dp 数组刚好完成了对因数的统计操作，此时 dp 数组的值如下：
dp = [4, 2, 1, 1]
因数有 1 的数有 4 个，因数有 2 的数有 2 个，因数有 3 和 4 的数有 1 个。故选 A。
5.C
由第 10 行 “p = max(p,a);” 可知，在 20 行循环执行前，p 的值就是 n 个数中的最大值，在 [18, 81, 54, 63] 中的最大值是 81，所以选 C。
6.A
可以去模拟题意。
初始化：dp[1] = 4;
dp[2] = 2;
dp[3] = 4;
dp[6] = 2;
dp[7] = 1;
dp[9] = 4;
dp[18] = 2;
dp[21] = 1;
dp[27] = 2;
dp[54] = 1;
dp[63] = 1;
dp[81] = 1;------------------------------------------
循环操作：
*注，"dp[2](1)" 表示 dp[2] 的值为 1i = 1
p = 81i = 2
dp[81](1) < 2, p--;
dp[80~64](0) < 2, p--;
dp[63](1) < 2, p--;
dp[62~55](0) < 2, p--;
dp[54](1) < 2, p--;
dp[53~28](0) < 2, p--;
p = 27i = 3
dp[27](2) < 3, p--;
dp[26~10](0) < 3, p--;
p = 9i = 4
p = 9
故输出为 “81 27 9 9”，选 A。
总结
以上为【CSP初赛练习】程序阅读9 的习题解析，希望大家喜欢！
这里是 YLCHUP，谢谢大家！
本文在 洛谷博客 同步发布。本人洛谷账号