Acwing第53场周赛 T2:整除子串反思

给定一个由数字组成的字符串 s，请你计算能够被 4 整除的 s 的子串数量。

子串可以包含前导 0。

例如，如果 s 为 124，则满足条件的子串有 4 个：12，4，24，124；如果 s 为 04，则满足条件的子串有 33 个：0，4，04。

输入格式

一个由数字组成的字符串 s。

输出格式

一个整数，表示满足条件的子串数量。

数据范围

前 4 个测试点满足 1≤|s|≤10。

所有测试点满足 1≤|s|≤3×105

输入样例1：

124

输出样例1：

4

输入样例2：

04

输出样例2：

3

输入样例3：

5810438174

输出样例3：

9

做的时候没出来，后来去y总直播间，

学到了：原来就是一个小学奥数题hh；

如果x（x的长度大于等于2）能整除4，那么x末尾两位组成的数字能整除4（充要条件）

待会儿会证明（并且研究能被N整除的数的特征）

那么只需要遍历一遍字符串就可以了

如果末尾两个符合添加，res+=i（i种选择）

注意两种特判：遍历时i = 0情况，由于遍历时，是研究以x[i]结尾的所有子串的情况，而以x[i]结尾的子串分两类，一类长度为1，一类长度>=2，长度为1特判一下；

#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
    ll res = 0;
    string x;
    cin >> x;
    if (x[0]%4==0) res++;
    for (int i = 1;i<x.size();i++)
    {
       if (((x[i]-'0')+10*(x[i-1]-'0'))%4 == 0) 
            res += i;
        if (x[i]%4==0) res++;
    }
    cout<<res;
    return 0;
}

研究能被N整除的数的特征（研究自然数）

N            限定条件 下面附手写证明图

奔赴热爱 奔赴山海!体会数学之美 算法之美