1. 题目解析与解题思路
1.1 T16：奇怪的比值问题
这道题目要求我们计算一个数N的所有因子之和与N本身的比值。题目中特别强调了以下几点需要注意：
- 因子包含1和N本身
- 需要处理N=1的特殊情况
- 输出结果保留两位小数
核心算法思路：
- 计算因子和时，可以采用遍历1到N的方法（法三），这是最直观的解法
- 更高效的解法是只遍历到sqrt(N)（法一和法二），这样可以减少循环次数
- 对于完全平方数需要特殊处理，避免重复计算相同的因子
注意：在优化算法中，当i是N的因子时，N/i也是N的因子。但当i=N/i时（即完全平方数），只需要加一次i的值。
1.2 T17：T的倍数N问题
这道题目要求找到一个满足特定条件的数字N：
- N以7结尾（即N=10×k+7）
- 将N的首位移到末尾得到的新数字M等于T×N
- N的范围在1到1,000,000之间
两种解法对比：
- 暴力枚举法（法一）：直接枚举所有可能的k值，计算对应的N和M，检查是否满足条件
- 数学推导法（法二）：通过数学公式推导，减少需要检查的候选数数量
数学推导关键点：
设N=10A+7，其中A是一个d位数（d≥0）
则M=7×10^d + A
根据条件M=T×N，可以推导出：
A = [7×(10^d - T)] / (10T - 1)
1.3 T18：三角形数字输出问题
这道题目要求按照特定规律输出数字三角形：
- 每行输出的数字数量等于行号
- 数字从给定的s开始，按1-9循环
- 不同三角形之间用空行分隔
实现要点：
- 使用双重循环控制行和列的输出
- 数字循环可以通过两种方式实现：
- 取模运算：cur = (cur % 9) + 1
- 条件判断：当cur>9时重置为1
- 注意输出格式，包括数字间的空格和三角形间的空行
2. 代码实现与优化分析
2.1 T16的三种实现方法
法一：平方根优化法
cpp复制#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main(){
int N;
while(cin>>N){
int sum=0;
if(N==1){
sum=1;
}
else{
sum =1+N;
for(int i=2;i<=sqrt(N);i++){
if(N%i==0){
if(i==N/i){
sum+=i;
}
else{
sum+=i+(N/i);
}
}
}
}
double t=static_cast<double>(sum)/N;
cout<<fixed<<setprecision(2)<<t<<endl;
}
return 0;
}
法二：平方根优化法的另一种写法
cpp复制#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main() {
int N;
while(cin >> N) {
int sum = 1 + N;
for(int i = 2; i * i <= N; i++) {
if(N % i == 0) {
if(i == N / i) {
sum += i;
} else {
sum += i + (N / i);
}
}
}
double t = static_cast<double>(sum) / N;
cout << fixed << setprecision(2) << t << endl;
}
return 0;
}
法三：直接遍历法
cpp复制#include <iostream>
#include <iomanip>
using namespace std;
int main() {
int n;
while (cin >> n) {
int sum = 0;
for (int i = 1; i <= n; i++) {
if (n % i == 0) {
sum += i;
}
}
double ratio = static_cast<double>(sum) / n;
cout << fixed << setprecision(2) << ratio << endl;
}
return 0;
}
2.2 T17的两种解法实现
法一：暴力枚举法
cpp复制#include <iostream>
using namespace std;
int main() {
int T;
int pow10[6] = {1, 10, 100, 1000, 10000, 100000};
while (cin >> T) {
bool found = false;
for (int k = 0; k <=99999; ++k) {
long long N = 10LL * k + 7;
if (N > 1000000) continue;
int d = 1;
if (N >= 100000) d = 6;
else if (N >= 10000) d = 5;
else if (N >= 1000) d = 4;
else if (N >= 100) d = 3;
else if (N >= 10) d = 2;
long long M = 7LL * pow10[d-1] + k;
if (M == T * N) {
cout << N << endl;
found = true;
break;
}
}
if (!found) {
cout << "No" << endl;
}
}
return 0;
}
法二：数学推导法
cpp复制#include <iostream>
using namespace std;
int main() {
int T;
long long pow10[6] = {1, 10, 100, 1000, 10000, 100000};
while (cin >> T) {
bool found = false;
for (int d = 0; d <= 5 && !found; ++d) {
long long m = 7 * (pow10[d] - T);
long long n = 10 * T - 1;
if (m >= 0 && m % n == 0) {
long long A = m / n;
if (d == 0) {
if (A != 0) continue;
} else {
if (A < pow10[d-1] || A >= pow10[d]) continue;
}
long long N = 10 * A + 7;
if (N <= 1000000) {
cout << N << endl;
found = true;
}
}
}
if (!found) {
cout << "No" << endl;
}
}
return 0;
}
2.3 T18的数字三角形实现
cpp复制#include <iostream>
using namespace std;
int main() {
int s, n;
int t = 0;
while (cin >> s >> n) {
if (t > 0) {
cout << endl;
}
t++;
int cur = s;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
if (j > 1) {
cout << " ";
}
cout << cur;
// 两种循环数字的方法
// 方法一：
cur = (cur % 9) + 1;
// 方法二：
/*
cur++;
if (cur > 9) {
cur = 1;
}
*/
}
cout << endl;
}
}
return 0;
}
3. 算法优化与性能分析
3.1 T16算法的时间复杂度
- 直接遍历法：时间复杂度O(N)，对于每个数需要检查1到N的所有数
- 平方根优化法：时间复杂度O(√N)，只需要检查1到√N的数
性能对比：
- 当N=1,000,000时：
- 直接遍历法需要1,000,000次循环
- 平方根优化法只需要1,000次循环
- 实际测试中，平方根优化法比直接遍历法快约1000倍
3.2 T17两种解法的效率对比
-
暴力枚举法：
- 需要枚举k从0到99,999
- 每次枚举需要计算N的位数和M的值
- 最坏情况下需要100,000次循环
-
数学推导法：
- 只需要枚举d从0到5
- 每次枚举只需要进行简单的数学运算
- 最多只需要6次循环
实际测试：
- 对于T=3的测试用例：
- 暴力枚举法需要检查k=0到k=2857才能找到N=2857
- 数学推导法只需要检查d=3即可直接计算出N=2857
3.3 T18的输出优化
虽然题目看起来简单，但在输出大量数据时，IO操作可能成为瓶颈。可以考虑以下优化：
- 使用'\n'代替endl，避免频繁刷新缓冲区
- 对于大规模输出，可以考虑先构建字符串再统一输出
- 数字到字符串的转换可以使用更高效的方法
4. 常见问题与调试技巧
4.1 T16常见错误
-
因子和计算错误：
- 忘记包含1和N本身
- 对于完全平方数重复计算因子
- 解决方法：仔细检查因子计算逻辑，特别是边界条件
-
浮点数精度问题：
- 直接使用int除法会导致精度丢失
- 正确做法：先将sum转换为double再除法
- 使用fixed和setprecision控制输出格式
4.2 T17调试技巧
-
中间变量打印：
- 在暴力枚举法中，可以打印k、N、d、M等中间变量
- 帮助理解算法执行过程，发现逻辑错误
-
边界条件测试：
- 测试T=1的情况（应该输出7）
- 测试T=10的情况（应该输出No）
- 测试大T值确保不会溢出
-
数学推导验证：
- 手动计算几个测试用例，验证推导公式的正确性
- 特别注意d=0和d=1的特殊情况
4.3 T18格式问题
-
空格控制：
- 每行第一个数字前不应有空格
- 后续数字前需要加空格
- 解决方法：使用j>1的条件控制空格输出
-
空行控制：
- 第一个三角形前不应有空行
- 后续三角形前需要空行
- 使用t变量记录已输出的三角形数量
-
数字循环：
- 确保数字在1-9之间正确循环
- 两种实现方法都要测试边界情况（从9到1的过渡）
5. 扩展思考与进阶问题
5.1 T16的进一步优化
-
质因数分解法：
- 先对N进行质因数分解
- 利用因子和的公式计算总和
- 对于大数可以进一步优化性能
-
预处理法：
- 预处理1到1,000,000所有数的因子和
- 查询时直接查表，适合多次查询的情况
5.2 T17的数学证明
-
公式推导的严谨性：
- 证明A必须是整数的条件
- 分析分母10T-1不能为0的情况（T=0.1，但T是整数）
- 讨论m≥0的条件对d的限制
-
解的唯一性：
- 证明对于给定的T，最多只有一个解
- 分析不同d值之间的关系
5.3 T18的变种问题
-
不同数字循环模式：
- 修改为其他循环模式，如斐波那契数列
- 实现自定义数字序列的循环
-
不同形状输出：
- 输出倒三角形、菱形等其他形状
- 调整循环结构实现不同输出模式
-
彩色输出：
- 使用ANSI颜色代码实现彩色数字输出
- 根据数字值或位置设置不同颜色
在实际编程竞赛中，这类题目考察的不仅是代码实现能力，更重要的是对问题的分析能力和算法优化能力。建议读者在理解基础解法后，尝试这些扩展问题，进一步提升编程能力。