#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';
        //位置2
		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';
		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)%p]++;
		sum+=dp[0];
	}
	cout<<sum;
	return 0;
} 

另外，超时原因是i j p使用long long，使用int可以通过，但二者的运行时间还是差距比较大，求大佬解惑