//第一段代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll dp[129],lst[129],p,sum;
string s;
int main(){
	cin>>p>>s;
	int n=s.size(); 
	for(int i=0;i<n;i++){
		int q=s[i]-'0';
		
		for(int j=0;j<p;j++)dp[(j*10+q)%p]+=lst[j];
		dp[(q)%p]++;
		sum+=dp[0];
        for(int j=0;j<p;j++)lst[j]=dp[j],dp[j]=0;//位置1
	}
	cout<<sum;
	return 0;
} 

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll dp[129],lst[129],p,sum;
string s;
int main(){
	cin>>p>>s;
	int n=s.size(); 
	for(int i=0;i<n;i++){
		int q=s[i]-'0';
		q%=p;
		for(int j=0;j<p;j++)lst[j]=dp[j],dp[j]=0;//位置2
		for(int j=0;j<p;j++)dp[(j*10+q)%p]+=lst[j];
		dp[q]++;
		sum+=dp[0];
	}
	cout<<sum;
	return 0;
} 

另外超时是因为循环中的i j p使用了long long，改成int能过。但是改成int之后这两段代码仍有很大的运行速度差别