题意：

给出n个ai，m个pi，$z_i=\sum\limits_{1 \le i \le n}\Bigl\lfloor \frac{a_i}{\lceil\log_{p}a_i\rceil}\Bigr\rfloor$，求$(\sum\limits_{i=1}^{m} i \cdot z_i) \bmod 10^9$。

$$1 \le n, m \le 5 \times 10^5$$ $$2 \le a_i \le 10^{9}$$ $$2 \le p_i \le 10^{9}$$

思路：

省赛的题目…在最后几分钟以为想到解法了其实是错觉…看到数学公式就一通打表，真的菜啊。

首先根据数据范围可以知道分母还是很小的，不超过30。

所以可以先预处理出来a[i]/分母，用前缀和存起来。

每给你一个p，对于每个分母，可以根据p二分出来ai的范围，落入这个范围的就用前缀和加一下就可以了。

这里内存有点紧…会SF…用sizeof预估一下内存吧…

这里有个地方很迷…$temp=(temp+pre[j][pos2]-pre[j][pos1-1]+MOD)%MOD$;我觉得加的不会是负的吧a[j]/i都是正的呀…对拍了一下各种数据也都是对的…然而似乎是会有负的…所以每次有减的取模的时候都加一下MOD吧…

代码：

ll a[500003];
ll pre[32][500003];//分母为i的式子的前缀和
int n;
void init()
{
    for(ll i=1;i<=30;i++)
    {
        pre[i][0]=0;
        for(int j=1;j<=n;j++)
            pre[i][j]=(pre[i][j-1]+a[j]/i)%MOD;
    }
}
int main()
{
    //printf("%d\n",sizeof(a)+sizeof(pre));
    int t,m;
    ll p;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            scanf("%lld",&a[i]);
        sort(a+1,a+n+1);
        init();
        ll ans=0;
        for(ll i=1;i<=m;i++)
        {
            scanf("%lld",&p);
            ll temp=0;
            ll l=1,r=p;//(p^(j-1),p^j]
            for(ll j=1;j<=30;j++)
            {
                int pos1=upper_bound(a+1,a+n+1,l)-a;
                int pos2=upper_bound(a+1,a+n+1,r)-a;
                pos2--;
                if(a[pos1]<=r)
                    temp=(temp+pre[j][pos2]-pre[j][pos1-1]+MOD)%MOD;
                l=r;r*=p;
                if(l>=a[n])break;
            }
            temp=(temp*i)%MOD;
            ans=(ans+temp)%MOD;
        }
        printf("%lld\n",ans);
    }
    return 0;
}