【ZOJ - 4029】Now Loading!!!（整除分块，思维，二分，前缀和）

题干：

其中 zi 是第i次询问后的z。

解题报告：

    因为有取log运算，所以分母的取值肯定不会超过30种，所以分每一个分母的时候，用前缀和优化一个和，最后求乘积就行了。（其实不需要快速幂，用快速幂也可以但是容易出错，因为需要判断如果已经大于1e9了就直接return到一个break的地方，但是wjh大佬强啊！！所以不怂、、）

另外这题要注意不能直接一个前缀和求出来之后向下取整，举个例子，1/3+1/3+1/3+1/3+1/3+1/3+1/3，正确答案应该是0，但是你这样直接分子前缀和求得的结果就是2，所以应该维护30个向下取整前缀和，就巧妙的优化了这个问题。

AC代码：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pair<int,int> PII;
const int MAX = 5e5 + 5;
const ll mod = 1e9;
ll a[MAX],p[MAX];
ll all[MAX][31];
ll qsm(ll a,ll b,int &ff) {
	ll t=1;
	int fl=0;
	while(b) {
		if(b&1) {
			t*=a;
			if(t>mod||fl) {
				ff=1;break;
			}
			t%=mod;
		}
		a*=a;
		if(a>mod) fl=1;
		a%=mod;
		b>>=1;
	}
	return t;
}
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 j = 1; j<=30; j++) {
			for(int i=1; i<=n; i++) {
				all[i][j]=all[i-1][j]+a[i]/j;
			}
		}
		ll ans=0;
		for(ll i=1; i<=m; i++) {
			ll tmp=0;
			scanf("%lld",&p[i]);
			for(ll j=1; j<=n;) {
				int ff=0;
				ll tt=(ll)ceil(log(a[j]*1.0)*1.0/log(p[i]*1.0));//求出大分母 
				ll maxx=qsm(p[i],tt,ff);
				if(ff) {
					ll sum1=all[n][tt]-all[j-1][tt];
					tmp=(tmp+sum1)%mod;
					break;
				}
				int pos=upper_bound(a+1,a+n+1,maxx)-a - 1; //找到最后一个小于等于他的。 
				ll sum=all[pos][tt]-all[j-1][tt];
				tmp=(tmp+sum)%mod;
				j=pos+1;
			}
			ans=(ans+i*tmp)%mod;
		}
		printf("%lld\n",ans%mod);
	}

	return 0;
}