[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;
}