F. Pairwise Modulo

想到了，但又沒完全想到。。wtcl

---

首先 $p_k=p_{k?1}+{\sum }_{1\le i<k}{a}_k\mathrm{m}\mathrm{o}\mathrm{d}{a}_i+{\sum }_{1\le i<k}{a}_i\mathrm{m}\mathrm{o}\mathrm{d}{a}_k$

${\sum }_{1\le i<k}{a}_k\mathrm{m}\mathrm{o}\mathrm{d}{a}_i={\sum }_{1\le i<k}(a_k??\frac{a_k}{a_i}?a_i)=(k?1)a_k?s$

考慮如何計(jì)算$s={\sum }_{1\le i<k}?\frac{a_k}{a_i}?a_i$

如果$k{a}_i\le a_k<(k+1)a_i$那么$?\frac{a_k}{a_i}?a_i=k{a}_i$，這個(gè)東西用樹狀數(shù)組維護(hù)一下，不太容易描述，詳細(xì)看代碼。

---

${\sum }_{1\le i<k}{a}_i\mathrm{m}\mathrm{o}\mathrm{d}{a}_k={\sum }_{1\le i<k}(a_i??\frac{a_i}{a_k}?a_k)={\sum }_{1\le i<k}{a}_i?t$

考慮如何計(jì)算$t={\sum }_{1\le i<k}?\frac{a_i}{a_k}?a_k$

不但發(fā)現(xiàn)對于任意兩個(gè)數(shù)$u,v$來說有下面規(guī)律$?\frac{u}{v}?v=kv,u\le kv<(k+1)v$

枚舉k，我們只需用統(tǒng)計(jì)出$\{a_i,1\le i<k\}$每段區(qū)間$a_i$的個(gè)數(shù)，就可以計(jì)算$t$

Code

#include<bits/stdc++.h> using namespace std; using ll=long long; template <class T=int> T rd() {T res=0;T fg=1;char ch=getchar();while(!isdigit(ch)) {if(ch=='-') fg=-1;ch=getchar();}while( isdigit(ch)) res=(res<<1)+(res<<3)+(ch^48),ch=getchar();return res*fg; } const int N=300010; template <typename T=int> struct Fenwick {const int n;T t[N];Fenwick(int n):n(n){memset(t,0,sizeof t);}void add(int k,T v){for(;k<=n;k+=k&-k) t[k]+=v;}T qsum(int k){T v=0;for(;k;k-=k&-k) v+=t[k];return v;}T get(int l,int r){return qsum(r)-qsum(l-1);} }; int n; int a[N]; int main() {n=rd();for(int i=1;i<=n;i++) a[i]=rd();Fenwick<ll> f1(300000),f2(300000); //f1計(jì)算s f2計(jì)算tll pre=0,ans=0;for(int i=1;i<=n;i++){ans+=1ll*a[i]*(i-1);//s_1ans+=pre;//t_1ans-=f1.qsum(a[i]);// s_2for(int j=a[i];j<=300000;j+=a[i]){int l=j,r=min(300000,j+a[i]-1);ans-=f2.get(l,r)*j;//t_2f1.add(l,a[i]);}f2.add(a[i],1);pre+=a[i];printf("%lld%c",ans," \n"[i==n]);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的codeforces1553 F. Pairwise Modulo（数学）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。