試し割りの素因数分解はlong longを使うと4倍以上遅い。intにせよ

• Quiz
  • Another Problem About Dividing Numbers https://codeforces.com/contest/1538/problem/D
• TLE
  • https://codeforces.com/contest/1538/submission/119039358
• AC✅
  • https://codeforces.com/contest/1538/submission/119077130
• 伝えたいこと
  • 制約 N=10⁴, A=10⁹ にて素因数分解したらTLEした。整数にはlong longを使っていた
  • intにしたら通った。大量の割り算をする時はint, long longの差が効いてくる？

D, long long -> intにしたら592msで通った。まじか、普段は数十msしか差がつかない印象だったのに

— peroon_cp💧 (@peroon_cp) June 10, 2021

// 計算量O(√N)
// なのでN=10^18だと間に合いません

// long long -> intとすると4倍(?)速くなります
// N=10^4, A=10^9の時は必要でしょう

// 素因数分解
// その素因数が何個あるかのmapを返す
map<ll, ll> factorize(ll n){
    map<ll, ll> mp;
    ll sq = sqrt(n);
    FOR(i, 2, sq+1){
        while(n%i==0){
            mp[i]++;
            n/=i;
        }
    }
    // 残り
    if(n!=1){
        mp[n]++;
    }
    return mp;
}