求$\displaystyle \sum_{i=1}^{n}\sum_{j=1 \land i \not = j}^{m}(n\ mod\ i)(m\ mod\ j) $

Input

第一行两个数 $n,m$。

Output

一个整数表示答案 mod 19940417的值

Sample Input

[cpp]3 4[/cpp]

Sample Output

[cpp]1[/cpp]
HINT样例说明
答案为
$(3mod1)(4mod2)+(3mod1)(4mod3)+(3mod1)(4mod4)+(3mod2)(4mod1)+(3mod2)(4mod3)+(3mod2)(4mod4)+(3mod3)(4mod1)+(3mod3)(4mod2)+(3mod3)*(4mod4)=1 $

数据规模和约定
对于100%的数据$n,m<=10^9 $ 。

#Source中国国家队清华集训 2012-2013 第一天

题解

        写再草稿纸上丢了。。。

code

[cpp]
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll%= 19940417;
const ll inv = 3323403;
inline ll sum(ll a,ll b) {
return (a+b)(b-a+1)/2%mod;
}
ll cal(ll n) {
ll tmp=0;
ll left, right;
for(ll i=1;i<=n;i=right+1) {
left = i;
right=n/(n/i);
tmp=(tmp+ n
(right-left+1)%mod – (n/i)sum(left,right))%mod;
}
return (tmp+mod)%mod;
}
ll sum2(ll x) {
return x
(x+1)%mod(2x+1)%modinv%mod;// sigma (i~n) = n(n+1)(2n+1)/6
//在数论中不能瞎除要乘以逆元
//使用扩欧算的 6对于mod的逆元是3323403
}
int main() {
ll n,m,ans=0;
scanf(“%lld %lld”,&n,&m);
ans = cal(n)*cal(m)%mod;
if(n>m) swap(n,m);
ll s1,s2,s3;
ll right,left;
for(ll i=1;i<=n;i=right+1) {
left = i;
right = min(n/(n/i),m/(m/i));

    s1 = n*m%mod * (right - left +1)%mod;
    s2 = (n/i)*(m/i)%mod * (sum2(right)-sum2(left-1)+mod)%mod;
    s3 = (n/i*m + m/i*n)%mod *sum(left,right)%mod;
    ans=(ans-(s1+s2-s3)%mod+mod)%mod;
}
return !printf("%lld\n",ans);

}
[/cpp]

分类: ACM数论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.