- 求(sum_{i=1}^nsum_{j=1}^m(nmod i)(mmod j)[i ot=j])。
- (n,mle10^9)
第一步：解除限制
考虑(i ot=j)这个限制使得(i)和(j)的贡献不能独立计算，因此我们先容斥处理掉它。
也就是说，用所有情况减去(i=j)的情况即为答案，得到下面这个式子：（不妨设(nle m)）
[sum_{i=1}^n(nmod i) imes sum_{j=1}^m(mmod j)-sum_{i=1}^{n}(nmod i)(mmod i)
]
(sum_{i=1}^n(nmod i))
求(sum_{i=1}^n(nmod i))是一个非常经典的问题。
由于(nmod i=n-lfloorfrac ni floor imes i)，所以原式相当于：
[sum_{i=1}^n(n-lfloorfrac ni
floor imes i)=n^2-sum_{i=1}^nlfloorfrac ni
floor imes i
]
显然后面这一项可以用除法分块轻松搞定。
(sum_{j=1}^m(mmod j))同理。
(sum_{i=1}^n(nmod i)(mmod i))
考虑仍旧按照之前的转化，得到：
[sum_{i=1}^n(n-lfloorfrac ni
floor imes i)(m-lfloorfrac mi
floor imes i)=n^2m-sum_{i=1}^n(m imes lfloorfrac ni
floor imes i+n imes lfloorfrac mi
floor imes i-lfloorfrac ni
floor imes lfloorfrac mi
floor imes i^2)
]
后面这家伙也是一个除法分块就能解决的。
综上所述，这道题就用除法分块做完了。
代码：(O(sqrt n))
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define X 19940417
#define I2 9970209
#define I6 3323403
#define S1(x) (1LL*I2*(x)%X*((x)+1)%X)//1+2+...+x
#define S2(x) (1LL*I6*(x)%X*((x)+1)%X*(2*(x)+1)%X)//1+4+9+...+x^2
using namespace std;
int n,m;
I int Q1(CI n)//求Σ(n%i)
{
RI t=0;for(RI l=1,r;l<=n;l=r+1) r=n/(n/l),//除法分块
t=(1LL*(n/l)*(S1(r)-S1(l-1)+X)+t)%X;return (1LL*n*n-t+X)%X;
}
I int Q2(CI n,CI m)//求Σ(n%i)(m%i)
{
RI t=0;for(RI l=1,r;l<=n;l=r+1) r=min(n/(n/l),m/(m/l)),//除法分块
t=((1LL*m*(n/l)+1LL*n*(m/l))%X*(S1(r)-S1(l-1)+X)+t)%X,
t=(t-1LL*(n/l)*(m/l)%X*(S2(r)-S2(l-1)+X)%X+X)%X;
return (1LL*n*n%X*m%X-t+X)%X;
}
int main()
{
return scanf("%d%d",&n,&m),n>m&&(n^=m^=n^=m),printf("%d
",(1LL*Q1(n)*Q1(m)-Q2(n,m)+X)%X),0;//强制n≤m
}