2757: [SCOI2012]Blinker的仰慕者 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1038 Solved: 291 Description Blinker 有非常多的仰慕者，他给每个仰慕者一个正整数编号。而且这些编号还隐藏着特殊的意义，即编号的各位数字之积表示这名仰慕者对Blinker的重要度。 现在Blinker想知道编号介于某两个值A,B之间，且重要度为某个定值K的仰慕者编号和。 Input 输入的第一行是一个整数N，表示Blinker想知道的信息个数。 接下来的N行，每行有三个数，A,B,K。表示 Blinker想知道编号介于A和B之间的，重要度为K的仰慕者的编号和。 Output 输出N行，每行输出介于A和B之间，重要度为 K的仰慕者编号和。结果可能很大， 模上20120427。 Sample Input 3 1 14 4 1 30 4 10 60 5 0<=K<=10^18 Sample Output 18 40 66 【样例解释】 第一组样例中，在 1到14之间各位数字之积等于 4的有 4和 14，故编号和为18。 HINT 【数据范围】 对于20%的数据，保证： 2<=A<=B<=1000000000，1<=N<=30 对于50%的数据，保证：2<=A<=B<=1000000000000000000，1<=N<=30 对于100%的数据，保证： 2<=A<=B<=1000000000000000000，1<=N<=5000
//Come On 上题解 #include<iostream> #include<cstring> #include<cstdio> #include<map> #include<cmath> #include<algorithm> #include<queue> #include<stack> using namespace std; #define LL long long const int Mod = 20120427; const LL INF = pow(9,18); const int N = 131313; LL id[N],sum[20][N],num[20][N],all_sum[20],all_num[20],pw[20]; int len; char bit[30]; inline int Insert_Hash(LL x){ int k=x%N; while(id[k]!=-1){ ++k; if(k>=N) x=0; } id[k]=x; return k; } int make_ID(LL x){ int k=x%N; while(id[k]!=x){ if(id[k]==-1) return -1; ++k; if(k>=N) k=0; } return k; } LL stk[N],tot; void pre_init(){ memset(id,-1,sizeof id ); memset(sum,0,sizeof sum );memset(num,0,sizeof num ); tot=0; pw[0]=1; for(int i=1;i<20;i++) pw[i]=pw[i-1]*10 % Mod; int r=0; for(int i=0;i<=9;i++){ if(make_ID(i)==-1){ Insert_Hash(i); stk[tot++]=i; } num[1][make_ID(i)]=1;sum[1][make_ID(i)]=i; } int tail=tot; for(int i=1;i<19;i++){ for(int j=0;j<tail;j++){ if(pow(9,i)<stk[j]) break; LL x=stk[j]; int s=make_ID(x),t; for(LL k=0;k<=9;k++){ if(make_ID(x*k)==-1){ Insert_Hash(x*k); stk[tot++]=x*k; } t=make_ID(x*k); num[i+1][t]=(num[i+1][t]+num[i][s])%Mod; sum[i+1][t]=(sum[i+1][t]+sum[i][s]+(k*(pw[i]*num[i][s])%Mod)%Mod)%Mod; } } sort(stk,stk+tot); tail=tot; } memset(all_num,0,sizeof all_num ); memset(all_sum,0,sizeof all_sum ); for(int i=0;i<20;i++) for(int j=0;j<N;j++){ all_num[i]=all_num[i]+num[i][j]; if(all_num[i]>=Mod) all_num[i]-=Mod; } for(int i=0;i<20;++i) for(int j=0;j<N;++j){ all_sum[i]=all_sum[i]+sum[i][j]; if(all_sum[i]>=Mod) all_sum[i]-=Mod; } } LL dfs_zero(int p,LL pre,bool zero,bool limit,bool first){ if(p==0) return zero ? pre : 0; if(!limit&&!first){ if(!zero) return ((((pre*pw[p])%Mod)*num[p][0])+sum[p][0])%Mod; else return ((((pre*pw[p])%Mod)*all_num[p])+all_sum[p])%Mod; } int tail=limit?bit[p]-'0':9; LL ret=0; for(LL v=0;v<=tail;v++){ ret+=dfs_zero(p-1,(pre*10+v)%Mod,zero||(v==0&&!first),limit&&v==tail,first&&v==0); if(ret>=Mod) ret-=Mod; } return ret; } LL dfs(int p,LL pre,LL K,bool limit,bool first){ if(p==0) return K==1 ? pre : 0; int t=make_ID(K); if(t==-1) return 0; if(!limit&&!first){ LL nm=num[p][t]; LL sm=sum[p][t]; return (((pre*nm)%Mod*pw[p])+sm)%Mod; } int tail=limit?bit[p]-'0':9; LL ret=0; for(LL v=0;v<=tail;++v) { if(first){ if(v==0){ ret+=dfs(p-1,(pre*10)%Mod,K,limit&&v==tail,first); if(ret>=Mod) ret-=Mod; } else if(K%v==0) { ret+=dfs(p-1,(pre*10+v)%Mod,K/v,limit&&v==tail,false); if(ret>=Mod) ret-=Mod; } } else if(v!=0&&(K%v)==0) { ret+=dfs(p-1,(pre*10+v)%Mod,K/v,limit&&v==tail,false); if(ret>=Mod) ret-=Mod; } } return ret; } int main (){ pre_init(); int T;cin>>T; while(T--){ LL x,y,K; scanf("%lld%lld%lld",&x,&y,&K); --x; sprintf(bit+1,"%lld",x); len=strlen(bit+1); reverse(bit+1,bit+1+len); LL ans=0; if(K==0) ans-=dfs_zero(len,0,false,true,true); else ans-=dfs(len,0,K,true,true); if(ans<0) ans+=Mod; sprintf(bit+1,"%lld",y); len=strlen(bit+1); reverse(bit+1,bit+1+len); if(K==0) ans+=dfs_zero(len,0,false,true,true); else ans+=dfs(len,0,K,true,true); if(ans>=Mod) ans-=Mod; printf("%lld\n",ans); } return 0; }