C++の約数とか使う時用の関数
なのでN=1e10とかなら動くはず。
vector<ll> divisor(ll M){ //約数の全列挙 vector<ll> dd; for(ll i = 1; i*i <= M; i++){ if(M % i == 0){ dd.push_back(i); if(i * i != M){ dd.push_back(M/i); } } } sort(dd.begin(), dd.end()); return dd; } vector<ll> factor(ll M){ //素因数分解 vector<ll> dd; if(M == 1){ dd.push_back(1); return dd; } for(ll i = 2; i*i <= M; i++){ while(M % i == 0){ dd.push_back(i); M /= i; } } if(M != 1) dd.push_back(M); sort(dd.begin(), dd.end()); return dd; }
よくある処理を使いやすい関数にまとめていく作業って大事。