题意：给定一个序列，多次询问

将a数组从小到大排序，下面那个值只有不超过32种，于是预处理f[i][j]，表示分母为i时，aj/i的前缀和是多少。

然后对于一个给定的p，一定将分母划分成了一些连续的段落，通过枚举这些分母，二分获得分母变化的位置，将区间和累计进答案。

注意，对于给定的p，一个分母控制的某段区间是a的元素属于p^i+1到p^(i+1)的这段。

复杂度log^2n。

#include
     
      //#include
      
       #include
       
        using namespace std;int f,cc;void R(int &x){    cc=0;f=1;    for(;cc<'0'||cc>'9';cc=getchar())if(cc=='-')f=-1;    for(x=0;cc>='0'&&cc<='9';cc=getchar())(x*=10)+=(cc-'0');    x*=f;}#define MOD 1000000000typedef long long ll;int T,n,m,a[35][500005];ll c[500005];//int poses[100005][35];//double Log(const int &p,const int &x){//	return log((double)x)/log((double)p);//}int main(){	R(T);	for(;T;--T){		R(n); R(m);		for(int i=1;i<=n;++i){			R(a[1][i]);		}		sort(a[1]+1,a[1]+n+1);		for(int i=1;i<=n;++i){			c[i]=(ll)a[1][i];		}		for(int i=1;i<=n;++i){			for(int j=2;j<=32;++j){				a[j][i]=a[1][i]/j;			}		}		for(int i=1;i<=32;++i){			for(int j=1;j<=n;++j){				a[i][j]=(a[i][j]+a[i][j-1])%MOD;			}		}//		for(int p=2;p*p<=MOD;++p){//			for(int i=1;i<=32;++i){//				if((int)(ceil(Log(p,c[n]))+0.5)
        
         >1);//					if((int)(ceil(Log(p,c[mid]))+0.5)>=i){//						r=mid;//					}//					else{//						l=mid+1;//					}//				}//				poses[p][i]=l;//			}//		}		int p;		ll ans=0;		int popo[35];		for(int zu=1;zu<=m;++zu){			R(p);//			if((ll)p*(ll)p<=(ll)MOD){//				for(int i=1;i<32;++i){//					if(poses[p][i]>n){//						break;//					}//					ans=(ans+((ll)zu*(ll)((a[i][poses[p][i+1]-1]-a[i][poses[p][i]-1]+MOD)%MOD))%(ll)MOD)%(ll)MOD;//				}//			}//			else{				ll pp=1;				for(int i=1;i<32;++i){					ll* be=upper_bound(c+1,c+n+1,pp);					if(be-c>n){						break;					}					pp*=(ll)p;					ans=(ans+((ll)zu*(ll)((a[i][upper_bound(c+1,c+n+1,pp)-c-1]-a[i][be-c-1]+MOD)%MOD))%(ll)MOD)%(ll)MOD;				}//			}		}		printf("%lld\n",ans);	}	return 0;}