d364 - 10637 - Coprimes
題目描述
題目要求找出將給定的數字 S 分解成 t 個互質正整數的所有可能組合。互質指的是這些數字的最大公因數為 1。輸出時，每個組合中的數字應按升序排列，並且按照類似字典順序輸出所有組合。
解題思路
這題使用深度優先搜尋 (DFS) 來找出所有可能的互質數字組合。c[i][j] 預先計算了 i 和 j 的最大公因數，以便在 DFS 過程中快速檢查互質性。
DFS 的基本思路是：
- 從第一個數字開始，嘗試所有可能的數值，從上一個數字的值開始。
- 對於每個嘗試的數字，檢查它是否與已經選擇的數字互質。
- 如果互質，則將其添加到當前組合中，並遞迴地尋找剩餘的數字。
- 如果找到
t個互質數字，並且它們的和等於S，則輸出該組合。
為了避免重複計算和提高效率，在遞迴過程中，可以限制嘗試的數字的上限，避免超出 S 的範圍。
複雜度分析
- 時間複雜度: O(101^t)，其中 t <= 30。最壞情況下，需要遍歷所有可能的組合。
- 空間複雜度: O(t)，主要用於儲存當前組合中的數字。
程式碼
#include <iostream>
using namespace std;
int c[101][101],n,ans[31],s,t;
int f( int a, int b ){
if( b==0 )
return a;
return f( b, a%b );
}
inline void dfs(int it,int d){
if(it==t&&d==0){
for(int i=0;i<it;++i){
cout << ans[i] ;
if(i<it-1)cout << ' ';
else cout << "\n";
}
return;
}
else if(it==t||d<ans[it-1])return;
int sn=d/(t-it);
for(int i=ans[it-1];i<=sn;++i){
int ch=1;
for(int j=0;j<it&&ch;++j)
if(c[ans[j]][i]!=1)ch=0;
if(ch){
ans[it]=i;
dfs(it+1,d-i);
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
for(int i=1;i<=101;++i)
for(int j=i;j<101;++j)
c[i][j]=f(i,j);
while(cin >> n){
for(int ca=1;ca<=n;++ca){
cin >> s >> t;
int sn=s/t;
cout << "Case " << ca << ":\n";
for(int i=1;i<=sn;++i){
ans[0]=i;
dfs(1,s-i);
}
}
}
}