首页 > itarticle > zoj4092

zoj4092

admin 11月 14, 2020 0

题意

求最后所给式子的和。

思路

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

代码


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 (){
    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;
            
            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=%dn",l,r);
                ans=(ans+sum[r-1][pos]-sum[l-1][pos])%mod;
                l=r;
                if(pp>a[n]) break;
            }
            //printf("ans=%lldn",ans);
            res=(res+i*ans%mod)%mod;
        } 
        printf("%lldn",res);
    }
    //system("pause");
}