题解 | #约数的个数#

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int yueshu(int n)
{
    int cnt = 2;
    double s = sqrt(n);
    if(n == 1)
        return 1;
    for(int i = 2;(double)i<=s;i++)
    {
        if( n%i == 0 && i!=s)
            cnt+=2;
        else if(n%i == 0)
            cnt++;
    }

    return cnt;
}

int main(void)
{

    int n;
    cin>>n;
    int a[n];
    for(int i = 0;i<n;i++)
    {
        cin>>a[i];
    }
    for(int i = 0;i<n;i++)
    {
        cout<<yueshu(a[i])<<endl;
    }

    return 0;
}

一开始的时候，没想那么多，直接暴力求解，然后发现时间过不去，考虑到肯定是很大的数据，于是需要根据约数的性质进行优化，可知约束肯定到根号就会停止，即到了根号，之后的约数，其实在前面就已经出现过了，例如在计入1的时候，其本身就已经出现，在计入2的时候，其本身的一半就已经计入，故每次查到一个约数的时候，总数加2。只有当计入其本身的根号时特殊为加1，故可作特殊判断，1的约数只有其自己，从2开始，约数至少有两个。