同題：UVa 11344 – The Huge One
老師出了一個程式作業給你的女友 Marry。(你沒有女友)
由於您你在寫程式方面是大神，因此你非常樂意幫助她。(工具人)
因為你計劃本週末和她一起去看電影，所以你不希望你的女友花太多時間在寫程式上。
如果你完成這項作業，Marry 會非常開心，並且可能在周末不只跟你看電影。(>/////<)
以下為 Marry 的作業：
給定數字 M (0 ≤ M ≤ 10^1000)，並且從間隔 [1 ~ 12] 之間挑選不同數字組成集合 S。此集合 S 中的所有數字均為整數。
如果數字 M 可被集合 S 中的所有數字整除，則稱其為「Wonderful」。請判斷數字 M 是否「Wonderful」。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 輸入第一行包含數字 N (0 < N ≤ 2000)，代表有幾組測資。 每組測資的第一行包含數字 M (0 ≤ M ≤ 10^1000)。 第二行包含集合 S 中的元素數量，以及集合中的數字。 第二行的數字皆由空格分隔。集合 S 元素皆在 [1 ~ 12] 的範圍內。 | 對於每組測資輸出一行： 如果數字 M 可被集合 S 中的所有數字整除 輸出「M – Wonderful.」 否則輸出「M – Simple.」。 M 請用相應的測資數字替換。 |
| 4 0 12 1 2 3 4 5 6 7 8 9 10 11 12 379749833583241 1 11 3909821048582988049 1 7 10 3 1 2 9 | 0 – Wonderful. 379749833583241 – Wonderful. 3909821048582988049 – Wonderful. 10 – Simple. |
解題思路
使用字串收 M，以下是如何判斷數字是否能被整除：
- 2: 個位數字是否是偶數
- 3: 所有位數的數字總和是否能被 3 整除
- 4: 最後兩位數是否能被 4 整除
- 5: 個位數字是否是 0 或 5
- 6: 能被 2 和 3 整除
- 7: 將數字分成三個數字一組 (從右到左)，輪流加減之後是否能被 7 整除
- 8: 最後三位數是否能被 8 整除
- 9: 所有位數的數字總和是否能被 9 整除
- 10: 個位數字是否為 0
- 11: 奇數位數的數字總和減偶數位數的數字總和是否能被 11 整除
- 12: 是否能被 3 和 4 整除
範例程式碼－ZeroJudge E535: The Huge One
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for (int i = 0; i<N; i++) {
string M;
cin >> M;
int S;
cin >> S;
bool ans = true;
for (int j = 0; j<S; j++) {
int num;
cin >> num;
if (num == 2) {
const int tmp = M[M.length()-1] - '0';
if (tmp % 2 != 0) ans = false;
}
else if (num == 3) {
int sum = 0;
for (int k = 0; k<M.length(); k++) {
sum += M[k] - '0';
}
if (sum % 3 != 0) ans = false;
}
else if (num == 4) {
if (M.length() >= 2) {
const int tmp = stoi(M.substr(M.length()-2, M.length()));
if (tmp % 4 != 0) ans = false;
}
else {
if (stoi(M) % 4 != 0) ans = false;
}
}
else if (num == 5) {
const char ch = M[M.length()-1];
if (ch != '0' && ch != '5') ans = false;
}
else if (num == 6) {
const int tmp = M[M.length()-1] - '0';
if (tmp % 2 != 0) ans = false;
int sum = 0;
for (int k = 0; k<M.length(); k++) {
sum += M[k] - '0';
}
if (sum % 3 != 0) ans = false;
}
else if (num == 7) {
int count = 0;
string tmp = "";
vector<int>v;
for (int k = M.length()-1; k>=0; k--) {
tmp += M[k];
count++;
if (count == 3) {
reverse(tmp.begin(), tmp.end());
v.push_back(stoi(tmp));
tmp = "";
count = 0;
}
}
if (tmp.length() > 0) {
reverse(tmp.begin(), tmp.end());
v.push_back(stoi(tmp));
}
int sum = 0;
for (int i = 0; i<v.size(); i++) {
if (i % 2 == 0) {
sum += v[i];
}
else sum -= v[i];
}
if (sum % 7 != 0) ans = false;
}
else if (num == 8) {
if (M.length() >= 3) {
const int tmp = stoi(M.substr(M.length()-3, M.length()));
if (tmp % 8 != 0) ans = false;
}
else {
if (stoi(M) % 8 != 0) ans = false;
}
}
else if (num == 9) {
int sum = 0;
for (int k = 0; k<M.length(); k++) {
sum += M[k] - '0';
}
if (sum % 9 != 0) {
ans = false;
}
}
else if (num == 10) {
if (M[M.length()-1] != '0') ans = false;
}
else if (num == 11) {
int odd = 0, even = 0;
for (int k = 0; k<M.length(); k++) {
if (k % 2 != 0) even += M[k] - '0';
else odd += M[k] - '0';
}
if ((even - odd) % 11 != 0) ans = false;
}
else if (num == 12) {
int sum = 0;
for (int k = 0; k<M.length(); k++) {
sum += M[k] - '0';
}
if (sum % 3 != 0) ans = false;
if (M.length() >= 2) {
const int tmp = stoi(M.substr(M.length()-2, M.length()));
if (tmp % 4 != 0) ans = false;
}
else {
if (stoi(M) % 4 != 0) ans = false;
}
}
}
if (M == "0") {
cout << "0 - Wonderful.\n";
continue;
}
if (ans) cout << M << " - Wonderful.\n";
else cout << M << " - Simple.\n";
}
}
//ZeroJudge E535
//Dr. SeanXD