백준 12116 - Uzastopni

https://www.acmicpc.net/problem/12116

 

힌트

$a$부터 연속된 $k$개의 정수의 합을 구하려면 다음과 같은 식으로 풀 수 있다.

 

$a \times k + \frac{k \times (k - 1)}{2}$

 

그 합이 $N$이 되려면

 

$N = a \times k + \frac {k \times (k - 1)}{2}$

 

를 만족해야 함을 알 수 있다.

풀이

힌트에서 언급한 식 $N = a \times k + \frac{k \times (k - 1)}{2}$ 를 만족하는 $a$를 구해보도록 하자.

 

식을 정리하면 $2N = k(2a + k - 1) \rightarrow 2a = \frac{2N}{k} - k + 1$가 되므로 적절한 범위의 $k$에 대해 $2a$가 짝수인 경우를 모두 찾아주면 된다.

 

이때, $k$의 범위는 $2N = k(2a + k - 1) \rightarrow k^{2} \leq 2N \rightarrow k \leq \sqrt{2N}$이므로 $\sqrt{2N}$ 이하의 모든 $k$에 대해 검사하면 효율적으로 답을 계산할 수 있다.

 

정답 코드 - CPP

// #pragma GCC target("fma,avx,avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
 
using namespace std;
using namespace __gnu_pbds;
 
using ll = int_fast64_t;
using pii = pair<int, int>;
// using oset = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
 
ll n;
 
void solve()
{
  cin >> n;
  ll nn = n + n;
 
  for (ll i = 2; i * i <= nn; i++)
  {
    if (nn % i != 0) continue;
    ll val = nn / i - i + 1;
    if (val & 1) continue;
    val >>= 1;
    cout << val << ' ' << val + i - 1 << '\n';
  }
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}