BOJ
BOJ::10504 덧셈
BOJ Gold 3
BOJ::10504 덧셈
- Link : BOJ::10504
- Link : 참고한 사이트
- Level : Gold 3
- tag : math
시사점
- 역시 수학 문제는 2가지가 중요하다는 점을 깨우쳐줍니다.
- 하나는, 손으로 써가면서 규칙을 찾는 것입니다.
- 손으로 써가며 다음과 같은 규칙들을 찾을 수 있었습니다.
- 홀수는 무조건 가능하다.
- 홀수 x에 대해(1이 아닌 x), x/2와 x/2+1이 가능합니다.
- 7 = 3 + 4
- 짝수 중 6의 배수는 항상 가능하다.
- 6의 배수는 3의 배수이기도 하므로, 항상 3가지 수로 나누어집니다.
- n = n/3 -1 , n/3, n/3 +1
- 그 외의 짝수는 규칙성을 찾았지만 글로 설명하기는 힘들 것 같습니다.
- 다른 하나는, 찾은 규칙을 수식으로 정리해나가는 것입니다.
- 하나는, 손으로 써가면서 규칙을 찾는 것입니다.
이해(x)
- n이 주어집니다.
- 연속되는 수의 합으로 n을 표현하려고 합니다.
- 불가능한 경우, “IMPOSSIBLE”을 출력하고,
- 가능한 경우, 수식으로 출력합니다.
설계, 손 코딩(x)
- 손으로 중심이 되는 코드를 구현합니다.
- 손으로 규칙을 찾았지만 2의 제곱수가 안된다는 사실을 발견하지 못하였고, 링크에 걸어둔 페이지를 참고하여 풀이했습니다.
- 결론적으로 등차수열의 합 공식을 이용합니다.
- k + (k+1) + … + (k + d - 1) = (2k + d - 1) * d / 2
- (2k + d - 1) * d = 2 * N
- 즉, k를 구하기 위해서 d >= 2 의 범위인 d를 찾아내면 됩니다.
- 또한 수식으로 풀이해볼때, d는 2 * N의 약수인 것을 알 수 있습니다.
- 이를 통해, 2 * N의 약수들을 구한 후 k를 찾아내는 방법으로 풀이할 수 있습니다.
- 또한, n이 2의 제곱수 형태인 경우 합으로 나타낼 수 없습니다
- 이 이유에 대해서 저는 단순히 충분한 수에 대해 테스트해봤기에 확인할 수 있었습니다.
- 공식에 의해 해당 현상이 발현하는 사유가 있을것으로 예상됩니다.
복잡도
- O(root(N))
구현(x)
// https://beenpow.github.io/
#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
//#define f first
//#define s second
#define all(v) (v).begin(), (v).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pair<int, int> >
#define vpll vector<pair<ll, ll> >
typedef long long ll;
using namespace std;
#define MOD 1000000007
ll n;
vll ans;
void PRINT(){
if(ans.size() == 0){
cout << "IMPOSSIBLE" << endl;
}else{
cout << n << " = " << ans[0];
rep(i, 1, ans.size()){
cout << " + " << ans[i];
}
cout << endl;
}
}
void process(){
ans.clear();
cin >> n;
vll dvrs;
ll n2 = 2 * n;
for(int i = 2; i * i <= n2; i++){
if( n2 % i == 0){
dvrs.push_back(i);
if(i != n2/i) dvrs.push_back(n2/i);
}
}
sort(all(dvrs));
bool f = false;
for(int i = 1; i < 32; i++){
if((1LL << i) == n) f = true;
}
if(!f){
rep(i, 0, dvrs.size()){
ll d = dvrs[i];
ll q = (2 * n ) / d;
ll r = (2 * n ) % d;
if(r > 0) continue;
ll k = q - d + 1;
if(q > 0 && (k%2 == 0)){
k /= 2;
for(ll j = k; j < k + d; j++)
ans.push_back(j);
break;
}
}
}
PRINT();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while(tc--)
process();
return 0;
}