題干：

其中 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; }

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【ZOJ - 4029】Now Loading!!!（整除分块，思维，二分，前缀和）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。