//1 + ... + n >= Kなる最小のnに着目すると、2回で必ず達成可能と分かり、1回でできるかの判定問題と分かる。 //和が(1+...+N)-Kになる区間を探せばよく、これは二分探索でも尺取りでもいい。 #include #define int long long using namespace std; int N, K; signed main() { int i, j; cin >> N >> K; int s = 0, aim = N * (N + 1) / 2 - K; j = 1; for (i = 1; i <= N; i++) { for (; j <= N; j++) { if (s >= aim) break; s += j; } if (s == aim) { //cout << i << ", " << j << ", s = " << s << endl; cout << 1 << endl; return 0; } s -= i; } cout << 2 << endl; return 0; }