G1001 [GESP202303 一级] 长方形面积 题解

难度：1（GeekPi教学评定）；知识点：循环枚举、因数、整数运算。

解题思路

把宽记为 w，则长只能为 A/w。依次枚举 w=1,2,…，只要 w*w≤A 且 A 能整除 w，就找到一种长方形。

为什么正确

每个合法长方形都恰有一个不大于长的宽；枚举覆盖所有这样的宽，且每个宽只计一次。

易错点

正方形也要统计，所以循环条件包含等号；不要同时统计长宽交换后的情况。

复杂度

时间：O(√A)；额外空间：O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a,c=0;
    cin>>a;
    for(int i=1;i*i<=a;i++)c+=a%i==0;
    cout<<c;
}

来源与说明

本题解为配套教学整理，非官方题解。题库使用自行生成的测试数据，5个测试点。