【洛谷P3245】【HNOI2016】大數

Description

https://www.luogu.org/problem/show?pid=3245

就是給一個數字字元串，問區間 [ l , r ] [l,r] [l,r]所有字串組成的數字有多少個是質數P的倍數。

Solution

把所有字尾的數字拿出來%P，記為 s i s_i si​，那麼如果 s l = s r + 1 s_l=s_{r+1} sl​=sr+1​，那麼 [ l , r ] [l,r] [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]);
}