[ boj : 4839 ] 소진법

www.acmicpc.net/problem/4839

4839번: 소진법

문제 : 수가 주어지고 소진법에 맞게 출력하여라

 

해설 : 흠...실버5 에바야~~~~~~~~~

일단 소수들의 곱을 이용하는 문제입니다. n의 범위가 적당하다면 에라토스체네스의체라든지 어떻게 해서 소수들을 쫙 구해둔 다음 하나씩 곱해보면 되지만 n이 21억이니 이 방법은 안되겠죠. 그러면 생각해볼게 문제의 범위를 이용하는 것 입니다. 직접 소수들을 곱해보세요. 그러면 29까지 곱하면 21억은 훌쩍 넘어가는 것을 알 수 있습니다.

우린 그러면 2부터 23까지의 9개의 소수들로만으로도 충분히 문제를 해결할 수 있다는 뜻이 되겠습니다.

 

별개로 구현이 빡쎄네요;;;;주의하셔서 잘 구현하시길 바라겠습니다.

전 벡터에 한 싸이클씩 담아주어서 역으로 출력하게끔 해주었습니다.

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll prime[] = { 2,3,5,7,11,13,17,19,23,29 };
vector<ll> v[10];

int main()
{
	ll n,t;
	while (true) {
		cin >> n;
		if (n == 0)break;
		t = n;

		int pos = 0;
		while (n > 1) {
			int i;
			ll x = 1;
			for (i = 0; i < 10 && x<=n; i++)
				x *= prime[i];
			x /= prime[--i];
			ll y = n / x;
			n %= x;
			v[pos].push_back(y);
			for (int j = 0; j < i; j++)
				v[pos].push_back(prime[j]);
			pos++;
		}
		if(n==1)
			v[pos++].push_back(n);
		cout << t << " = ";
		for (int i = pos - 1; i >= 0; i--) {
			for (int j = 0; j < v[i].size();j++) {
				cout << v[i][j];
				if (j != v[i].size() - 1)
					cout << "*";
			}
			if(i!=0)
				cout << " + ";
		}
		cout << "\n";
		for (int i = 0; i < 10; i++)
			v[i].clear();
	}
	return 0;
}