题解：B4184 [中山市赛 2024] 除法运算

_Pioneer_ · 2025-02-25 20:20:41 · 题解

这道题第一感觉就是暴力，即枚举从１到 n+1 作为除数的商。

#include<bits/stdc++.h>
using namespace std;
long long t,n,a[10000000];
int main()
{
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        int p=1,cnt=0;
        for(int i=n+1;i>=1;i--){
            int k=n/i;
            if(k==p)continue;
            else a[++cnt]=k,p=k;
        }
        cout<<cnt<<endl;
        for(int i=1;i<=cnt;i++)cout<<a[i]<<" ";
        cout<<endl;
    }
    return 0;
}

然而，不出意外，TLE了一半。

所以优化是本题的关键。枚举的时候可以联想到判断一个数是否为素数时，仅需枚举到 \sqrt{n}。

同理，此题我们处理除数时，枚举到 i 时，同时将 n/i 压入数组内，枚举到 \sqrt{n} ，最后再用 sort 排列一下就行了。（需要注意当 n 为完全平方数时仅需压入一个）

完整代码

#include<bits/stdc++.h>
using namespace std;
long long t,n,a[10000000];
int main()
{
    scanf("%lld",&t);
    while(t--){
        scanf("%lld",&n);
        int cnt=1;
        a[cnt]=0;
        for(int i=1;i<=sqrt(n);i++){
            if(n/i==i)a[++cnt]=i;
            else {a[++cnt]=i;a[++cnt]=n/i;}
        }
        sort(a+1,a+cnt+1);
        cout<<cnt<<endl;
        for(int i=1;i<=cnt;i++)cout<<a[i]<<" ";
        cout<<endl;
    }
    return 0;
}