【題解】ZeroJudge d418: 00993 – Product of digits

【題目敘述】https://zerojudge.tw/ShowProblem?problemid=d418
【解題想法】

  •  Q 中所有數字(digit)的乘積等於 N,表示 Q 的每一個位數都是 N 的因數。
  • 因為要找出最小的 Q,對 N 做因數分解時,從 9 開始做到 2。 
  • 【例】N = 126 = 9 * 7 * 2,Q = 279。
  • 【例】N = 65 = 3 * 13,13 > 9 故無解。
#include <iostream>
#include <vector>
using namespace std;

int main() {
	int T, N;
	cin >> T;
	while (T--) {
		cin >> N;
		if (N == 1) {
			cout << "1\n";
			continue;
		}
		int digit[10] = {0}; 
		for (int i=9; i>1; i--) {
			while (N % i == 0) {
				digit[i]++;
				N /= i;
			}
			if (N == 1) break;
		}
		if (N == 1) {
			long long ans = 0;
			for (int i=2; i<=9; i++) {
				while (digit[i]--) {
					ans = ans * 10;
					ans += i;
				}
			}
			cout << ans <<'\n';
		} else {
			cout << "-1\n";
		}
	}
	return 0;
}
分享本文 Share with friends