UVa 11344 The Huge One：模性质

UVa 11344 The Huge One：模性质2014-07-07 synapse7 http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2319

简单点的方法：由于a*10%m=（（a%m）*10）%m，所以一个数一个数挨个取模判断即可。

复杂点的方法：

1. 1不用判断。

2. 若一个整数的未尾三位数能被8整除，则这个数能被8整除。

若一个整数的末尾两位数能被4整除，则这个数能被4整除。若一个整数的个位能被2整除，则这个数能被2整除。3. 若一个整数的数字和能被9整除，则这个整数能被9整除。

若一个整数的数字和能被3整除，则这个整数能被3整除。

4. 若一个整数能被2和3整除，则这个数能被6整除。

若一个整数能被3和4整除，则这个数能被12整除。

5. 若一个整数的末位是0，则这个数能被10整除。

若一个整数的末位是0或5，则这个数能被5整除。

6. 判定被7、11整除的简易方法（但此方法还不如上面的取模快）

7. 简化判断次数：

若8ok，则4,2ok；

若9ok，则3ok；

若2,3ok,则6ok；

若3,4ok，则12ok；

若10ok，则5ok。

完整代码：

01./*0.022s*/02.03.#include<cstdio>04.#include<cstring>05.06.char s[1005];07.int a[15];08.09.int main（）10.{11.int t, len, n, i, j, rem;12.bool f;13.scanf（"%d", &t）;14.while （t--）15.{16.getchar（）;17.gets（s）;18.len = strlen（s）;19.scanf（"%d", &n）;20.for （i = 0; i < n; ++i）21.scanf（"%d", &a[i]）;22.f = false;23.for （i = 0; i < n; ++i）24.{25.rem = 0;///remainder26.for （j = 0; j < len; ++j）27.rem = （rem * 10 + （s[j] & 15）） % a[i];28.if （rem）29.{30.f = true;31.break;32.}33.}34.if （f） printf（"%s - Simple.
", s）;35.else printf（"%s - Wonderful.
", s）;36.}37.return 0;38.}