Quotient - 商の集合
(lib/30-math/Quotient.cpp)

• View this file on GitHub
• Last update: 2023-06-26 06:47:35+09:00

• Quotient
• N/i の集合と個数を返す
• 提出

Verified with

• test/math/Quotient.test.cpp

Code

/*
 * @title Quotient - 商の集合
 * @docs md/math/Quotient.md
 */
inline static vector<pair<long long,long long>> Quotient(long long n) {
    assert(n > 0);
    long long b = sqrtl(n);
    long long l = b;
    while(n / l != b) ++l;
    vector<pair<long long,long long>> res = {{0,0}};
    for(long long i = 1; i <= l; ++i) {
        long long k = n / i;
        if(res.back().first == k) res.back().second++;
        else res.emplace_back(k,1);
    }
    for(long long i = b, r; 1 <= i; --i, l = r+1) {
        r = n / i;
        long long k = n / l;
        if(res.back().first == k) res.back().second = (r-l+1);
        else res.emplace_back(k,r-l+1);
    }
    reverse(res.begin(),res.end());
    res.pop_back();
    return res;
}

#line 1 "lib/30-math/Quotient.cpp"
/*
 * @title Quotient - 商の集合
 * @docs md/math/Quotient.md
 */
inline static vector<pair<long long,long long>> Quotient(long long n) {
    assert(n > 0);
    long long b = sqrtl(n);
    long long l = b;
    while(n / l != b) ++l;
    vector<pair<long long,long long>> res = {{0,0}};
    for(long long i = 1; i <= l; ++i) {
        long long k = n / i;
        if(res.back().first == k) res.back().second++;
        else res.emplace_back(k,1);
    }
    for(long long i = b, r; 1 <= i; --i, l = r+1) {
        r = n / i;
        long long k = n / l;
        if(res.back().first == k) res.back().second = (r-l+1);
        else res.emplace_back(k,r-l+1);
    }
    reverse(res.begin(),res.end());
    res.pop_back();
    return res;
}

Back to top page