[算法总结] 约数 !

吐槽:

好多定理啊

分解质因数 AcWing 872. 最大公约数 库函数

bits/stdc++.h
__gcd(a,b);

871. 约数之和(O√n +M log M) 细节:

因为ai的范围是 2e9+10

所以 如果使用 On的暴力枚举是必然超过的

借用@Bug-Free一张图

///若d > √n 是 N的约数
///则 N/d  n;

    while (n -- )
    {
        int x;
        cin >> x;
        auto res = get_divisors(x);

        for (auto x : res) cout  x;

        for (int i = 2; i  1) primes[x] ++ ;
    }

    LL res = 1;
    for (auto p : primes)
    {
        LL a = p.first, b = p.second;
        LL t = 1;
        while (b -- ) t = (t * a + 1) % mod;
        res = res * t % mod;
    }

    cout