Gym-100814K 数位DP 模拟除法

Johnny is a brilliant mathematics student. He loves mathematics since he was a child, now he is working on his PhD thesis. He faces a small mathematical problem, he has a n digit integer number (let us call it s) , he wants to find how many substring of s are divisible by a prime number p.

His supervisor professor is on vacation now, so can you play his role and help him with that?

https://cn.vjudge.net/contest/174050#problem/K

#include <bits/stdc++.h>

#include <cstring>

#include <iostream>

#include <algorithm>

#define INF 30000000

#define MOD 1000000007

#define mem(a,b) memset((a),b,sizeof(a))

#define TS printf("!!!\n")

#define pb push_back

#define pai pair<int,int>

#define ref(i,x,y)for(int i=x;i<=y;++i)

#define def(i,x,y)for(int i=x;i>=y;--i)

//std::ios::sync_with_stdio(false);

using namespace std;

//priority_queue<int,vector<int>,greater<int>> que;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pai1;

const double EPS=1e-;

const double PI=acos(-);

//next_permutation

int T,n,p,number[],s[],t[];

unsigned long long a,b;

int main()

{

    scanf("%d",&T);

    ref(i,,T)

    {

                //freopen("input.txt","r",stdin);

                //freopen("out.txt","w",stdout);

        cin>> a >> b >> n >> p;

        ref(i,,n)

        {

            number[i]=a*/b;

            a=a*;

            a%=b;

        }

        if(p==||p==||p==)

        {

            long long ans=;

            ref(i,,n)if(number[i]%p==)ans+=i;

            cout<< ans<< endl;

            continue;

        }

        int tmp=;

        s[n+]=;

        def(i,n,)

        {

            s[i]=(s[i+]+tmp*number[i])%p;

            tmp=tmp*%p;

        }

        ref(i,,p)t[i]=;

        def(i,n+,)t[s[i]]++;

        long long ans=;

        ref(i,,p-)

        if(t[i]>)ans+=1LL*t[i]*(t[i]-)/;

        cout<< ans<< endl;

    }

}