跳转至

试除法求约数

869.试除法求约数

给定 \(n\) 个正整数 \(a_i\)，对于每个整数 \(a_i\)，请你按照从小到大的顺序输出它的所有约数。

如果 \(x\) 是 \(n\) 的约数，则 \(\frac{n}{x}\) 也是 \(n\) 的约数，我们令 \(x\) 是 \(x、\frac{n}{x}\) 中最大的，则:

若 \(x = \frac{n}{x}\)，则 \(x = \frac{n}{x} = sqrt(n)\)

若 \(x < \frac{n}{x}\)，则 \(x < sqrt(n)\)

我们只要从 \(1\) 一直枚举到 \(sqrt(n)\)，就可以求出所有的约数。

由于 \(sqrt(n)\) 的时间消耗有点大，我们要用 for(int i = 2; i <= n / i; i ++) 取代 for (int i = 2; i <= sqrt(n); i ++)

关于约数个数的估计：

若对于正整数 \(n\)，约数个数 \(r(n) < sqrt(3n)；\)

若 \(n > 1260\)，约数个数 \(r(n) < sqrt(n)\)

对于 \(10^{18}\) 范围的整数，约数个数最多为：

\(10^5\)

代码参考：

const int N = int (1e7 + 10);
int x[N], y[N];

// 获取约数
void get_ds(int n)
{
    x[0] = y[0] = 0;
    for (int i = 1; i <= n / i; i ++)
    {
        if (!(n % i))
        {
            x[++ x[0]] = i;
            if (n / i == i) continue;
            y[++ y[0]] = n / i;
        }
    }
}

869.试除法求约数

给定 \(n\) 个正整数 \(a_i\)，对于每个整数 \(a_i\)，请你按照从小到大的顺序输出它的所有约数。

代码参考 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>

using namespace std;
int debuggersum = 0;

// 即使是不成熟的尝试，

const int N = int (1e7 + 10);
int x[N], y[N];

// 获取约数
void get_ds(int n)
{
    x[0] = y[0] = 0;
    for (int i = 1; i <= n / i; i ++)
    {
        if (!(n % i))
        {
            x[++ x[0]] = i;
            if (n / i == i) continue;
            y[++ y[0]] = n / i;
        }
    }
}

void solve(void)
{
    int n, t; scanf ("%d", &n);
    while (n --)
    {
        scanf ("%d", &t);
        get_ds(t);
        for (int i = 1; i <= x[0]; i ++) printf ("%d ", x[i]);
        for (int i = y[0]; i; i --) printf ("%d ", y[i]);
        puts("");
    }
}

// 也胜于胎死腹中的策略。

int main(void)
{
    ifstream fi; ofstream fo;
    fi.open("./lrq.in"); fo.open("./lrq.out");
    if (fi.is_open() && fo.is_open())
    {
        fo << "start running ..." << endl; fo.close(); fi.close();
        for (long long i = 1; i <= 4e8 + 2e7; i++);
        FILE *fin = freopen("./lrq.in", "r", stdin);
        FILE *fout = freopen("./lrq.out", "w", stdout);
        solve(); fclose(fin); fclose(fout);
    }
    else solve();

    return 0;
}