[TIOJ] 1067. C.互質任務
題目連結: http://tioj.infor.org/problems/1067 直接DP餘數即可，因為餘數$gcd(a, b) = gcd(a%b, b)$ #include <bits/stdc++.h> using namespace std; const int N = 1000 + 5; const int C = 10000 + 5; inline int gcd(int a, int b){return b?gcd(b, a%b):a;} int dp[2][C]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); bool me=0, he=1; int n, m; while(cin >> n >> m, n or m) { memset(dp[me], -1, sizeof(dp[me])); dp[me][0] = 0; for(int i=0;i<n;i++){ int x; cin >> x; for(int j=0;j<m;j++) if(dp[me][j] >= 0) { dp[he][j] = max(dp[he][j], dp[me][j]); dp[he][(j*10+x)%m] = max(dp[he][(j*10+x)%m], dp[me][j]+1); } memset(dp[me], -1, sizeof(dp[me])); swap(me, he); } int ans = 0; for(int i=0;i<m;i++) if(gcd(i, m) == 1){ ans = max(ans, dp[me][i]); } cout << ans << '\n'; } return 0; }