[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...