d183 - 00725 - Division
題目描述
題目要求找出兩個五位數的整數，使得第一個數除以第二個數的商為給定的 N (2 <= N <= 79)，並且兩個五位數包含 0 到 9 的所有數字各一次。
解題思路
程式使用暴力法，遍歷所有可能的五位數 i (從 1234 到 99999)，然後計算 n * i。接著，檢查 n * i 和 i 是否都是五位數，並且它們包含的數字是否為 0 到 9 的排列。check 函數用於驗證兩個數字是否滿足這個條件，它使用一個陣列 a 來記錄每個數字出現的次數，如果每個數字都恰好出現一次，則返回 true。如果找到符合條件的數對，則輸出結果，否則輸出 "There are no solutions for N."。
複雜度分析
- 時間複雜度: O(90000 * 10) = O(900000)。因為需要遍歷 1234 到 99999 之間的數，並且
check函數需要 O(10) 的時間。 - 空間複雜度: O(10)。
check函數使用一個大小為 10 的陣列a來記錄數字出現的次數。
程式碼
#include <bits/stdc++.h>
using namespace std;
int a[15]; //存每個number出現的次數
bool check(int c,int d){
memset(a,0,sizeof(a));
//判斷是否>5位
if(d > 98765) return false;
//判斷是否出現重複
for(int i = 0;i < 5;i++){ //需要循環5次,判斷每一位
a[c % 10]++;a[d % 10]++;
c /= 10;d /= 10;
}
for(int i = 0;i < 10;i++){
if(a[i] != 1) return false;
}
return true;
}
int main(void){
int n,kase = 0;
while(scanf("%d",&n) == 1 && n){
if(kase++ > 0) printf("\n");
bool flag = false;
for(int i = 1234;i < 99999;i++){
if(check(i,n * i)){
printf("%05d / %05d = %d\n",n*i,i,n);
flag = true;
}
}
if(flag == false){
printf("There are no solutions for %d.\n",n);
}
}
return 0;
}