Time Limit: 1 Second
Memory Limit: 131072 KB
DreamGrid has integers . DreamGrid also has
for a given number
, where
,
.
Input
There are multiple test cases. The first line of input is an integer
The first line contains two integers and () -- the number of integers and the number of queries.
The second line contains integers ().
The third line contains integers ().
It is guaranteed that neither the sum of all nor the sum of all exceeds .
Output
For each test case, output an integer , where is the answer for the -th query.
Sample Input
2 3 2 100 1000 10000 100 10 4 5 2323 223 12312 3 1232 324 2 3 5
Sample Output
11366 45619
Author:
LIN, Xi
Source:
The 15th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
【题意】
对于每一次询问，求上式的值
【分析】
把a排序
由于分母的范围很小 [2,30]，可以枚举；
对于每一次询问p，枚举分母 i 时，可以找出a中分母等于 i 的那一段，预处理前缀和，用于此时直接加。
复杂度n * log * log
【代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
const int INF=0x3f3f3f3f;
const int mod=1e9;
int n,m;
int a[500010],p;
int sum[32][500010];
ll qpow(ll n,ll m)
{
ll ans=1;
while(m){
if(m&1)ans*=n;
n*=n;
m>>=1;
if(ans>20001001000)return -1;
}
return ans;
}
int main()
{
int T;cin>>T;
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+1+n);
for(int i=1;i<=31;i++) //pre sum of a/log
{
sum[i][0]=0;
for(int j=1;j<=n;j++)
sum[i][j]=(sum[i][j-1]+a[j]/i)%mod;
}
ll ans=0;
for(int k=1;k<=m;k++)
{
scanf("%d",&p);
ll res=0;
for(int i=1;i<=31;i++) //log p ai
{
ll down=qpow(p,i-1); //> it
ll up=qpow(p,i); // <=it
if(down==-1)break;
int l=1,r=n+1,mid;
if(down!=-1)
while(l<r){
mid=(l+r)>>1;
if(a[mid]>down)r=mid;
else l=mid+1;
}
int L=r;
l=1,r=n+1;
if(up!=-1)
while(l<r){
mid=(l+r)>>1;
if(a[mid]>up)r=mid;
else l=mid+1;
}
int R=r-1;
if(L>n)break;
if(L>R)continue;
res=(res+sum[i][R]-sum[i][L-1])%mod;
res=(res+mod)%mod;
}
ans=(ans+res*k%mod)%mod;
}
printf("%lld\n",ans);
}
}