96pts WA#14

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

typedef long long LL;

const int N = 200010;

int n, p, m;
char str[N];

namespace Solve1
{
    LL f[N], g[N];
    
    void Main()
    {
        for (int i = 1; i <= n; i ++ )
        {
            f[i] = f[i - 1], g[i] = g[i - 1];
            if ((str[i] - '0') % p == 0)
            {
                f[i] ++ ;
                g[i] += i;
            }
        }
        
        while (m -- )
        {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", g[r] - g[l - 1] - (f[r] - f[l - 1]) * (l - 1));
        }
    }
}

namespace Solve2
{
    int len;
    LL s[N], cnt[N], ans[N];
    vector<int> nums;
    struct Query
    {
        int l, r, id;
    }q[N];
    
    int get(int x)
    {
        return x / len;
    }
    
    bool cmp(Query& x, Query& y)
    {
        int i = get(x.l), j = get(y.l);
        if (i != j) return i < j;
        return x.r < y.r;
    }
    
    void add(int x, LL& res)
    {
        res += cnt[x];
        cnt[x] ++ ;
    }
    
    void del(int x, LL& res)
    {
        cnt[x] -- ;
        res -= cnt[x];
    }
    
    void Main()
    {
        len = sqrt(n);
        s[ ++ n] = 0;
        for (int i = n - 1, k = 1; i; i -- )
        {
            s[i] = (s[i + 1] + (str[i] - '0') * k % p) % p;
            k = k * 10ll % p;
            nums.push_back(s[i]);
        }
        nums.push_back(0);
        
        sort(nums.begin(), nums.end());
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        
        for (int i = 1; i <= n; i ++ )
            s[i] = lower_bound(nums.begin(), nums.end(), s[i]) - nums.begin();
        
        for (int i = 1; i <= m; i ++ )
        {
            int l, r;
            scanf("%d%d", &l, &r);
            q[i] = {l, r + 1, i};
        }
        
        sort(q + 1, q + m + 1, cmp);
        
        LL res = 0;
        for (int i = 0, j = 1, k = 1; k <= m; k ++ )
        {
            int l = q[k].l, r = q[k].r, id = q[k].id;
            while (i < r) add(s[ ++ i], res);
            while (i > r) del(s[i -- ], res);
            while (j < l) del(s[j ++ ], res);
            while (j > l) add(s[ -- j], res);
            ans[id] = res;
        }
        
        for (int i = 1; i <= m; i ++ )
            printf("%lld\n", ans[i]);
    }
}

int main()
{
    scanf("%d%s%d", &p, str + 1, &m);
    n = strlen(str + 1);
    if (p == 2 || p == 5) Solve1 :: Main();
    else Solve2 :: Main();
    
    return 0;
}