题目大意：给定一个数字（<=3*10^5）,判断其能被4整除的连续子串有多少个
解题思路：注意一个整除4的性质： 若bc能被4整除,则a1a2a3a4...anbc也一定能被4整除；
利用这个性质，先特判第一位数字是否能被4整除，可以则++cnt，
之后从第二位数字开始，设当前位为i,先判断a[i]能否被4整除，可以则++cnt,
再判断a[i-1]*10+a[i]能否被4整除，可以则cnt = cnt + (i)
相关证明： 设一整数各个位置为a1,a2,a3,...,an,b,c;
则(a1a2a3...an b c)%4 =( (a1a2a3...an)*100 + bc ) % 4
= (a1a2a3...an)*100 % 4 + (bc)%4 = 0 + (bc)%4 = (bc)%4 (100能被4整除)
注意，此题数据很大，要用long long
/* CF 628B New Skateboard --- 水题 */ #include <cstdio> #include <cstring> char s[300005]; int main() { #ifdef _LOCAL freopen("D:\\input.txt", "r", stdin); #endif while (scanf("%s", s) == 1){ long long len = strlen(s); long long cnt = 0; long long num; //处理前第一个数 num = s[0] - ‘0‘; if (num % 4 == 0){ ++cnt; } for (long long i = 1; i < len; ++i){ //判断当前位以及往前的位 num = s[i] - ‘0‘; if (num % 4 == 0){ ++cnt; } num = (s[i - 1] - ‘0‘) * 10 + s[i] - ‘0‘; if (num % 4 == 0){ cnt += i; } }//for(i) printf("%lld\n", cnt); } return 0; }
原文：http://www.cnblogs.com/tommychok/p/5370505.html
