d418 - 00993 - Product of digits

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個整數 N，要求找到最小的自然數 Q，使得 Q 的所有數字的乘積等於 N。如果找不到這樣的 Q，則輸出 -1。

解題思路

這個問題的核心是將給定的數字 N 分解成質因數，然後將這些質因數轉換成數字，並按照從小到大的順序排列，以得到最小的 Q。如果 N 無法分解成 2 到 9 之間的數字的乘積，則 Q 不存在，輸出 -1。

程式碼首先讀取測試案例的數量，然後對於每個案例，讀取輸入的整數 N。如果 N 小於 10，則直接輸出 N。否則，程式碼嘗試將 N 分解成 2 到 9 之間的質因數。在分解過程中，程式碼從 9 開始向下嘗試，如果 N 可以被 i 整除，則將 i 轉換成字元並添加到字串 b 中，然後將 N 除以 i。如果 N 無法被 2 到 9 之間的任何數字整除，則說明 Q 不存在，輸出 -1。最後，程式碼將字串 b 倒序輸出，得到最小的 Q。

複雜度分析

• 時間複雜度: O(log N) (因為每次除以一個因子，N 的大小會減少，最壞情況下需要除 log N 次)
• 空間複雜度: O(log N) (字串 b 的最大長度取決於 N 的大小，最壞情況下需要存儲 log N 個數字)

程式碼

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
	int a;
	cin >> a;
	while(a--){
		long long int c;
		cin >> c;
		string b;
		if(c<10){
			cout << c;
		}
		else{
			while(c!=1){
				bool k=1;
				for(int i=9;i>=2;i--){
					if(c%i==0){
						b+=i+48;
						c/=i;
						k=0; 
					}
				}
				if(k==1){
					cout << -1;
					b.clear();
					break;
				}
			}
		}
		for(int i=b.length()-1;i>=0;i--)
			cout << b[i];
		cout <<"\n";
	}
}