【洛谷P3245】【HNOI2016】大数

Description

https://www.luogu.org/problem/show?pid=3245
就是给一个数字字符串，问区间$[l,r]$所有字串组成的数字有多少个是质数P的倍数。

Solution

把所有后缀的数字拿出来%P，记为$s_i$，那么如果$s_l=s_{r+1}$，那么$[l,r]$就是P的倍数。
当然有例外，两个后缀拼接的时候是以10为底数的，如果P=2或5就不符合，所以特判即可。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<map>
#define fo(i,j,k) for(int i=j;i<=k;++i)
#define fd(i,j,k) for(int i=j;i>=k;--i)
using namespace std;
typedef long long ll;
const int N=1e5+10;
char S[N];
int z[N],cn[N];
ll s[N];
map<int,int> mp;
int be[N];
struct node{
    int l,r,p;
}b[N];
ll an[N];
bool cmp(node x,node y){
    return be[x.l]<be[y.l] || (be[x.l]==be[y.l] && x.r<y.r);
}
ll ans=0;
void add(int x) {
    ans+=cn[s[x]],cn[s[x]]++;}
void del(int x) {
    cn[s[x]]--,ans-=cn[s[x]];}
int n,P;
void pre(){
    fo(i,1,n){
    s[i]=s[i-1],cn[i]=cn[i-1];if((S[i]-'0')%P==0) s[i]+=i,++cn[i];}int m;scanf("%d",&m);while(m--){
    int l,r;scanf("%d %d",&l,&r);printf("%lld\n",s[r]-s[l-1]-(ll)(cn[r]-cn[l-1])*(l-1));}
}
int main()
{
    scanf("%d",&P);scanf("%s",S+1);n=strlen(S+1);int tmp=1;if(P==2 || P==5) return pre(),0;fd(i,n,1) s[i]=((ll)s[i+1]+(ll)(S[i]-'0')*tmp)%P,tmp=10ll*tmp%P,z[++z[0]]=s[i];sort(z+1,z+n+1);int mx=1;mp[z[1]]=mx;fo(i,2,n) mx+=z[i]!=z[i-1],mp[z[i]]=mx;fd(i,n+1,1) s[i]=mp[s[i]];int _n,tt=1,t=0;for(_n=1;_n*_n<n;_n++);fo(i,1,n+1){
    t++,be[i]=tt;if(t==_n) t=0,tt++;}int m;scanf("%d",&m);fo(i,1,m) scanf("%d %d",&b[i].l,&b[i].r),++b[i].r,b[i].p=i;sort(b+1,b+m+1,cmp);int l=1,r=1;cn[s[1]]=1;fo(i,1,m){
    while(l<b[i].l) del(l++);while(r>b[i].r) del(r--);while(l>b[i].l) add(--l);while(r<b[i].r) add(++r);an[b[i].p]=ans;}fo(i,1,m) printf("%lld\n",an[i]);
}