perogram

D - DivRem Number 約数列挙 約数一覧

Quiz

https://atcoder.jp/contests/diverta2019/tasks/diverta2019_d

Submit

解法

  • 8 = 3x2 + 2 = (3+1)x2
  • 8 = 1x7 + 1 = (7+1)x1
  • ここでmはそれぞれ3, 7
  • (約数-1)で全探索すればいい

計算量

  • 素因数分解 O(sqrt(N))
  • 約数列挙 1000000000000 = 1012 = 約数24個
    • 224 = 16777216 = 1.6 x 107 に収まる

感想

  • unratedコンテストになってしまったね
  • 約数列挙の関数を作っていなかったので、ビット全探索などやや高度なことをした気になっていたが、振り返るとそうでもない
  • 振り返り時には約数列挙の関数を作った。これからは再利用していく

他の人の解法

追記:約数高速列挙 (√N)

https://qiita.com/LorseKudos/items/9eb560494862c8b4eb56

追記:これとか

// 約数一覧を返します
vector<ll> calc_devisors(ll a){
    vector<ll> ret;
    for(ll i=1; i*i<=a; i++){
        if(a%i!=0) continue;
        ret.push_back(i);
        ll another = a/i;
        if(i!=another) ret.push_back(another);
    }
    sort(ALL(ret), greater<ll>()); // 使いやすいように大きい順にソートしておく
    return ret;
}