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

Quiz

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

Submit

• コンテスト中
  • https://atcoder.jp/contests/diverta2019/submissions/5361687
• コンテスト後 整理ver
  • https://atcoder.jp/contests/diverta2019/submissions/5369617

解法

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

計算量

• 素因数分解 O(sqrt(N))
• 約数列挙 1000000000000 = 10¹² = 約数24個
  • 2²⁴ = 16777216 = 1.6 x 10⁷ に収まる

感想

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

他の人の解法

• https://atcoder.jp/contests/diverta2019/submissions/5369855
• Nがaで割れるなら、a, N/aを約数としてsetに登録
• 後は同様に(約数-1)で、お気に入りの数かを全探索
• 10⁶までforすれば十分なのがポイント

追記：約数高速列挙 （√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;
}

追記：2020/06/22

• 制約10¹²
• sqrt(N)ならいけるな
• といえば約数
• 素因数分解してみる

約数列挙 log(a) ?

• spfで事前準備するVER
• verified https://atcoder.jp/contests/arc115/submissions/22316432