B4185题解

· · 题解

思路：

这道题如果暴力枚举子串，那么时间复杂度 O(n^2)，肯定超时。

正解应该是用数学的方法，首先，我们要知道，一个数如果是 5 的倍数，那么它的末位一定是 5 的倍数。一个数如果是 4 的倍数，那么它的末两位一定是 4 的倍数。

证明：一个正整数一定可以写成 x\times100+y 的形式，其中 x 为任意自然数， y 为小于 100 的自然数。那么 x\times100 一定是 4 的倍数，所以是否能被 4 整除取决于 y 是否能被 4 整除，而 y 其实就是数的末两位（另一个证明也差不多)。

到这思路已经非常清晰了，枚举 i 为子串末尾，判断末尾是否是 4 或 5 的倍数，如果末尾是 4 或 5 的倍数，那么以此为末尾的子串都符合要求。

代码：

#include<bits/stdc++.h>
using namespace std;
string a;
long long sum=0;//记的开long long 
int main()
{
    cin>>a;
    int n=a.size();
    for(int i=0;i<n;i++)
     {
        //注意：由于i是从0开始的，所以计数时要加1 
        if((a[i]-'0')%5==0) sum+=i+1;//判断5的倍数 
        else if(i>0&&((a[i-1]-'0')*10+a[i]-'0')%4==0)//判断末两位是4的倍数 
         {
            if((a[i]-'0')%4==0) sum++;//判断第i个数是4的倍数 
            sum+=i;
         }
        else if((a[i]-'0')%4==0) sum++;//判断第i个数是4的倍数 
     }
    cout<<sum;
    return 0;
}