4388: GESP C++六级样题_4亲朋数

#include <iostream>
using namespace std;
char S[1000001];
long long st_old[128];
long long st_new[128];
int main() {
    int p = 0;
    cin >> p;
    cin >> S;
    for (int i = 0; i < p; i++)
        st_old[i] = 0;
    long long res = 0;
    for (int t = 0; S[t] != '\0'; t++) {
        for (int i = 0; i < p; i++)
            st_new[i] = 0;
        int d = S[t] - '0';
        for (int i = 0; i < p; i++)
            st_new[(i * 10 + d) % p] += st_old[i];
        st_new[d % p]++;
        res += st_new[0];
        for (int i = 0; i < p; i++)
            st_old[i] = st_new[i];
    }
    cout << res << endl;
    return 0;
}