【題目敘述】https://zerojudge.tw/ShowProblem?problemid=f502
#include <bits/stdc++.h>
using namespace std;
int n, k, re[100], nxt[100];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--){
cin >> n >> k;
memset(re, 0, sizeof(re));
re[0] = 1;
bool flag = false;
for (int i = 0, a; i < n; i++){
cin >> a;
if (flag) continue;
a %= k;
for (int j = 0; j < k; j++){
if (!re[j]) continue;
nxt[(j+a+k)%k] = 1;
nxt[(j-a+k)%k] = 1;
}
flag = true;
for (int i = 0; i < k; i++){
re[i] = nxt[i];
if (!nxt[i]) flag = false;
else nxt[i] = 0;
}
}
if (re[0]) cout << "Divisible\n";
else cout << "Not divisible\n";
}
}
Python code (credit: Amy Chou)
ZeroJudge的測資可能存在多餘的字元富豪,Python會TLE(讀不到資料?)改用Virtual Judge可以AC,連結在此。
T = int(input().strip())
for Case in range(T):
n, k = map(int, input().strip().split())
A = list(map(int, input().strip().split()))
A = [a%k for a in A]
#print(A)
re = [0 for _ in range(k)]
nxt = [0 for _ in range(k)]
re[0] = 1
flag = False
for i in range(n):
for j in range(k):
if re[j] == 0:
continue
nxt[(j+A[i]+k)%k] = 1
nxt[(j-A[i]+k)%k] = 1
re = nxt
nxt = [0 for _ in range(k)]
if re[0] == 1:
print("Divisible")
else:
print("Not divisible")