백준 7868 해밍 수열

문제

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

7868번: 해밍 수열

 

풀이

문제 정의대로 수열에 있는 모든 수는 p1^x * p2^y * p3^z (x,y,z>=0인 자연수)꼴이다.

대표적인 소수가 2가 있다. 수 제한은 10^18이다. 2^60부터 10^18보다 커진다.

따라서 x,y,z는 p1,p2,p3가 무엇이든지 60보다 작다.

따라서 빈 배열을 선언하고 3중반복문으로 수들을 배열에 다 넣으면 된다.

for (int i =0;i<=60;i++) {
	for (int j =0;j<=60;j++){
		for(int k =0;k<=60;k++){
			ll x = pow(p1,i)*pow(p2*j)*pow(p3*j);
			if (1 < x < pow(10,18)){
				vt.pushback(x);
            }	
		}
	}
}

1을 포함하지 않게 주의하자.

 

그리고 정렬하고 출력하면 된다. 굳이 상수커팅할 필요 없다. 60은 4중반복문도 가능한 숫자이다.