주어진 자연수를 연속된 자연수의 합으로 표현하는 방법의 수는 주어진 수의 홀수 약수의 개수와 같다라는 정수론 정리가 있습니다.
라는 정수론 정리를 나중에 알았다.
public static void main(String args[]) {
int answer = 0;
for (int i = 1; i <= num; i += 2) {
if (num % i == 0) {
answer++;
}
}
return answer;
}
이면 간단히 정리가 되는걸 몰랐기에
연속된 자연수의 합의 형태로 표현되는 조건을 홀수 짝수 나눠서 계산헀다.
class Solution {
public int solution(int n) {
int answer = 0;
//k는 나누는 수, n은 몫
//짝수 2n+1 4n+2 6n+3 -> k x n + k/2
// n, n+1
// n-1 n n+1 n+2
// n-2 n-1 n n+1 n+2 n+3
//...
//홀수 k x n 의 형태로 표현 가능
//n의 약수 구하기
for(int i=1; i<n; i++){
int temp = n/i;
int rest = n%i;
//홀수
if(i%2==1){
if(rest==0){//나머지가 0이라면 k x n 형태인지 검증
if(temp > i/2){ //자연수 범위 내에서 가능한지 검증
// System.out.println(i);
answer++;
}
}else{
//해당x
}
//찍수
}else{
if(temp*i+i/2==n){ //k x n + k/2 와 n 이 같은지 검증
if(temp> (i/2)-1){ //자연수 범위내에서 가능한지 검증
// System.out.println(i);
answer++;
}
}
}
}
return answer;
}
}