bzoj2956: 模积和

2019-04-13 14:16发布

站内文章 / 模拟电子
17174 0 1778
显然分块搞搞。。 原式=(Σn%i)*(Σm%i)-Σ(n%i)*(m%i) 其中Σ(n%i)*(m%i)=Σn*m-i*(n/i*m+m/i*n)+i*i*(n/i)*(m/i)，分块搞搞即可，时间复杂度O(sqrt(n))。 #include #include #define ll long long #define MO 19940417 #define si 3323403 using namespace std; ll n,m,Sn,Sm,S3,Ans; ll Mod(ll x) { if (x<0) return x+MO; if (x>=MO) return x-MO; return x; } int main() { scanf("%lld%lld",&n,&m); if (n>m) swap(n,m); Sn=n*n%MO;Sm=m*m%MO;S3=Sn*m%MO; for (ll i=1,j;i<=n;i=j+1) { j=min(n,n/(n/i)); Sn=Mod(Sn-(n/i)*((i+j)*(j-i+1)/2%MO)%MO); } for (ll i=1,j;i<=m;i=j+1) { j=min(m,m/(m/i)); Sm=Mod(Sm-(m/i)*((i+j)*(j-i+1)/2%MO)%MO); } for (ll i=1,j;i<=n;i=j+1) { j=min(n,min(n/(n/i),m/(m/i))); //= S3-(m/i*n+n/i*m) *(i+j) *(j-i+1)/2 +(n/i)*(m/i) *(j*(j+1) *(2*j+1) -(i-1)*i *(2*i-1) )/6 ; S3=Mod(S3-(m/i*n+n/i*m)%MO*((i+j)*(j-i+1)/2%MO)%MO+(n/i)*(m/i)%MO*(j*(j+1)%MO*(2*j+1)%MO-(i-1)*i%MO*(2*i-1)%MO)%MO*si%MO); } printf("%lld ",Mod(Sn*Sm%MO-S3)); }

热门文章