AcWing 869. 试除法求约数

简介

什么是约数：如果一个数a除以另一个数b的余数为0，即 a%b == 0, 则b是a的约数。

如何求一个数x的所有约数：

用 x 除以 1 到 x 的所有数，如果余数是0，则把除数加到答案中。

优化

如果 a / b = c···0，则一定有 a / c = b····0。所以一个数 x 的约数肯定是成对存在的，对称轴是 根号x。
因此，只需要用 x 除以 1 到 根号x 之间的数，如果余数是0，则把除数以及x / 除数加到答案中。

比如 8 / 4 = 2 ···0 那么一定有 8 / 2 = 4 ·····0,所以x（这里是8）得约束成对存在（2和4）对称轴是根号x，即为二倍根号2

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void) {
    int T;
    cin >> T;
    while(T--){
        int n;
        cin >> n;
        vector<int> res;
        //约数成对存在，只需要循环到根号x
        // 不用i * i <= n，因为可能会溢出
        for(int i = 1;i<=n/i;i++){
            if(n % i == 0)
            {
                res.push_back(i);
                //如果i * i = x，添加i就行了，不需要添加x / i
                if(n/i != i)
                    res.push_back(n/i);
            }
        }
        sort(res.begin(),res.end());
        for(auto x : res) cout << x <<  " ";
        cout << endl;
    }
}