c548. Boook 愛鴿子

---

解法一、DFS

✅ 完整代碼

評分結果(參考) ： AC (12ms, 3.3MB)

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n, k;
vector<int> a;

int m = 0;
vector<int> ans(100001);

void dfs(int sum, int idx, int cnt){
    if(sum%k == 0) m = cnt;
    if(idx >= n) return;
    
    if(m == 0){
        ans[cnt] = idx+1;
        dfs(sum+a[idx], idx+1, cnt+1);
    }
    if(m == 0){
        dfs(sum, idx+1, cnt);
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> k;
    a.resize(n);
    for(int& i : a) cin >> i;
    dfs(0, 0, 0);
    
    cout << m << "\n";
    for(int i=0; i<m; i++){
        cout << ans[i] << " ";
    }
    
    return 0;
}