AT5361题解

きりと · 2021-04-02 10:50:10 · 题解

题目传送门

题目大意

见中文翻译。

解题思路

思维题，关键点在于要想出线性求字串数量的方法。

先给出结论：在大多数情况下，如果两个字串所对应的数字 \bmod p 所得的余数相等，且一个串是另一个的末尾某一段，则他们相减后得到的串符合要求。

证明：设第一个数为 a+x ，第二个数为 b+x ， a ，b 均为 p 的倍数，则在十进制下两数相减得到的差值也为 p 的倍数，然后此差值可以写成 c+10^x，当 10 的质因子中不含 p 时，结论成立。

解决方法：当 p=2 或 p=5 时特判，另外情况可以参见代码内的注释。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10,M=1e4+10;
char s[N];
int cnt[M];      //cnt[i]表示余数为i的数在之前出现了几次
signed main()
{
    int n,p,ans=0;
    cnt[0]=1;
    cin>>n>>p;
    cin>>s+1;
    if(p==2||p==5)
    {
        for(int i=1;i<=n;i++)
        {
            if((s[i]-'0')%p==0)
            {
                ans+=i;    //2，5的倍数都是只看个位，所以个位能被整除就可以+i
            }
        }
    }
    else
    {
        int t=1,r=0;
        for(int i=n;i>=1;i--)
        {
            r+=(s[i]-'0')*t%p;      //r记录当前位置所构成的数字%p的余数
            r%=p;
            ans+=cnt[r];      //更新答案
            cnt[r]++;
            t*=10;         //t记录10的x次方
            t%=p;
        }
    }
    cout<<ans<<endl;
    return 0;
}