自动搬运

查看原文

来自洛谷，原作者为

	guoshengyu1231 **

搬运于2025-08-24 21:17:41，当前版本为作者最后更新于2025-02-26 18:34:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

这道题如果暴力枚举子串，那么时间复杂度 $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;
}