[AtCoder] ABC 169 D – Div Game
問題
方針
任意の素数 \( p\) について \( N \bmod p^m = 0\) となるような最大の正の整数 \( m \) が求められたとします。この素数 \( p\) に関して、操作回数を最大化するには、\( c = 1, 2, 3, \cdots \) と選べば良いので、
\[ \dfrac{n(n+1)}{2} \leq m\]
と満たす最大の \( n \) が操作回数となります。このような \(n\) は二分探索によって求めることができます。\( m \) の求め方は、\( \sqrt{N} \) までの範囲で探索すれば十分です。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int bs(int a) { int l = 0; int r = 3 * a; while (r - l > 1) { int m = (l + r) / 2; if (m * (m + 1) <= 2 * a) { l = m; } else { r = m; } } return l; } int main() { ll N; cin >> N; vector<ll> a; ll t = N; for (ll i = 2; i * i <= N; i++) { int k = 0; while (t % i == 0) { t /= i; k++; } if (k != 0) a.push_back(k); } int ans = 0; if (t != 1) ans = 1; for (int i : a) { ans += bs(i); } cout << ans << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません