「BZOJ2956」模积和
Description
求∑∑((n mod i)*(m mod j))其中1<=i<=n,1<=j<=m,i≠j。
Input
第一行两个数n,m。
Output
一个整数表示答案mod 19940417的值
Sample Input
3 4
Sample Output
1
样例说明
答案为(3 mod 1)*(4 mod 2)+(3 mod 1) * (4 mod 3)+(3 mod 1) * (4 mod 4) + (3 mod 2) * (4 mod 1) + (3 mod 2) * (4 mod 3) + (3 mod 2) * (4 mod 4) + (3 mod 3) * (4 mod 1) + (3 mod 3) * (4 mod 2) + (3 mod 3) * (4 mod 4) = 1数据规模和约定
对于100%的数据n,m<=10^9。
样例说明
答案为(3 mod 1)*(4 mod 2)+(3 mod 1) * (4 mod 3)+(3 mod 1) * (4 mod 4) + (3 mod 2) * (4 mod 1) + (3 mod 2) * (4 mod 3) + (3 mod 2) * (4 mod 4) + (3 mod 3) * (4 mod 1) + (3 mod 3) * (4 mod 2) + (3 mod 3) * (4 mod 4) = 1数据规模和约定
对于100%的数据n,m<=10^9。
题解
\[\sum_{i=1}^{n}\sum_{j=1 \land i \not = j}^{m}(n\ mod\ i)(m\ mod\ j)\]
\[=\sum_{i=1}^{n}\sum_{j=1}^{m}(n-{\left \lfloor \frac{n}{i} \right \rfloor}i)(m-{\left \lfloor \frac{m}{j} \right \rfloor}j)-\sum_{i=1}^{min(n,m)}(n-{\left \lfloor \frac{n}{i} \right \rfloor}i)(m-{\left \lfloor \frac{m}{i} \right \rfloor}i)\]
\[=\sum_{i=1}^{n}\sum_{j=1}^{m}(n-{\left \lfloor \frac{n}{i} \right \rfloor}i)(m-{\left \lfloor \frac{m}{j} \right \rfloor}j)-\]\[\sum_{i=1}^{min(n,m)}(nm+{\left \lfloor \frac{n}{i} \right \rfloor}{\left \lfloor \frac{m}{i} \right \rfloor}i^2-(m{\left \lfloor \frac{n}{i} \right \rfloor}+n{\left \lfloor \frac{m}{i} \right \rfloor})i)\]
\[=\sum_{i=1}^{n}\sum_{j=1}^{m}(n-{\left \lfloor \frac{n}{i} \right \rfloor}i)(m-{\left \lfloor \frac{m}{j} \right \rfloor}j)-\sum_{i=1}^{min(n,m)}(n-{\left \lfloor \frac{n}{i} \right \rfloor}i)(m-{\left \lfloor \frac{m}{i} \right \rfloor}i)\]
\[=\sum_{i=1}^{n}\sum_{j=1}^{m}(n-{\left \lfloor \frac{n}{i} \right \rfloor}i)(m-{\left \lfloor \frac{m}{j} \right \rfloor}j)-\]\[\sum_{i=1}^{min(n,m)}(nm+{\left \lfloor \frac{n}{i} \right \rfloor}{\left \lfloor \frac{m}{i} \right \rfloor}i^2-(m{\left \lfloor \frac{n}{i} \right \rfloor}+n{\left \lfloor \frac{m}{i} \right \rfloor})i)\]
推完用上喜闻乐见的分块即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<set> #include<map> #include<vector> #define inf 1000000000 #define mod 19940417 #define ine 3323403 #define ll long long using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } ll n,m,ans; ll sum(ll a,ll b) { return (b-a+1)*(a+b)/2%mod; } ll sum2(ll x) { return x*(x+1)%mod*(2*x+1)%mod*ine%mod; } ll cal(ll n) { ll tmp=0; for(ll i=1,j;i<=n;i=j+1) { j=n/(n/i); tmp=(tmp+n*(j-i+1)%mod-sum(i,j)*(n/i))%mod; } return (tmp+mod)%mod; } int main() { n=read();m=read(); ans=cal(n)*cal(m)%mod; if(n>m)swap(n,m); ll s1,s2,s3; for(int i=1,j;i<=n;i=j+1) { j=min(n/(n/i),m/(m/i)); s1=n*m%mod*(j-i+1)%mod; s2=(n/i)*(m/i)%mod*(sum2(j)-sum2(i-1)+mod)%mod; s3=(n/i*m+m/i*n)%mod*sum(i,j)%mod; ans=(ans-(s1+s2-s3)%mod+mod)%mod; } printf("%lld\n",ans); return 0; } |
Subscribe
计数器 9855241
OI 课件=>
OI 课件=>