ZOJ4092

发表于 | 分类于

ZOJ4092

题意

​ 求最后所给式子的和。

思路

​ 因为2的30次方大于1e9，所以分母范围只可能是1-30，枚举分母预处理所有情况的前缀和，最后二分查找答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+10; 
const int mod=1e9;
ll a[maxn],p[maxn];
ll sum[maxn][31];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=30;j++){
                sum[i][j]=sum[i-1][j]+a[i]/j;
            }
        }
        ll res=0;
        for(int i=1;i<=m;i++){
            scanf("%d",&p[i]);
            ll pp=p[i];
            ll ans=0;
            //printf("i=%d\n",i);
            int l=1,r=1;
            for(int pos=1;pos<=30;pp*=p[i],pos++){
                r=upper_bound(a+1,a+n+1,pp)-a;
                //printf("l=%d r=%d\n",l,r);
                ans=(ans+sum[r-1][pos]-sum[l-1][pos])%mod;
                l=r;
                if(pp>a[n]) break;
            }
            //printf("ans=%lld\n",ans);
            res=(res+i*ans%mod)%mod;
        } 
        printf("%lld\n",res);
    }
    //system("pause");
}