因为一个矩形可以视为两个线段，一个是 x 方向的，一个是 y 方向的，上面的公式的两个乘数分别与其对应
这样一来我们就可以预处理出 y 方向上的所有 “线段”，再枚举 x 方向的每个 “线段” ，然后去 y 方向上去找到对应的与其匹配即可
不过需要特判一下 sum = 0 的情况，下面考虑一下 0 的贡献，假设 s[ i ] == 0，那么会使得 b 数组的第 i 行和第 i 列的取值都是 0，一行会产生 n * ( n + 1 ) / 2 个满足条件的子矩阵，而第 i 行和第 i 列同时为 0 的话，就会产生 n * ( n + 1 ) / 2 * 2 = n * ( n + 1 ) 个子矩阵，不过需要注意一下，b[ i ][ i ] 这个格子被计算了两次，所以需要减去
那么假设字符串 s 中共有 cnt[ 0 ] 个 “线段” 的取值为 0，那么这些 “线段” 既有 x 方向上的，又有 y 方向上的，根据上面容斥的扩展，总共是有 cnt[ 0 ] * n * ( n + 1 ) - cnt[ 0 ] * cnt[ 0 ] 个满足条件的子矩阵
代码：
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;char s[N];LL cnt[N];int sum[N];int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.ans.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int a;scanf("%d",&a);scanf("%s",s+1);int n=strlen(s+1);for(int i=1;i<=n;i++)sum[i]=sum[i-1]+s[i]-'0';for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)cnt[sum[i]-sum[j-1]]++;if(a==0){printf("%lld\n",cnt[0]*n*(n+1)-cnt[0]*cnt[0]);return 0;}LL ans=0;for(int i=1;i<=n;i++)for(int j=1;j<=i;j++){int num=sum[i]-sum[j-1];if(num!=0&&a%num==0&&a/num<N)ans+=cnt[a/num];}printf("%lld\n",ans);return 0;
}
