\(Description\)
求
答案对\(19940417\)取模。
\(n,m\leq10^9\)
\(Solution\)
如果不考虑\(i\neq j\)这个条件,根据和式的分配率答案就是
其中\(\sum_{i=1}^nn\ mod\ i=\sum_{i=1}^nn-\lfloor\frac{n}{i}\rfloor\times i\),接下来就可以通过数论分块\(O(\sqrt n)\)计算答案了(详细可见这道题)。
考虑怎么在这两项的乘积当中减去\(i=j\)的部分。
常数项可单独算,其余两项也都可用数论分块求得。
一个坑点是模数不是质数,在计算\(\sum_{i=l}^ri和\sum_{i=l}^ri^2\)时不能用费马小定理去乘2和6的逆元,但可以通过扩展欧几里得来求。可以,但没必要(手动滑稽)。
#include<complex>
#include<cstdio>
using namespace std;
const int mod=19940417;
int n,m,ans;
int Calc1(int x)
{
long long res=0;
for(int l=1,r;l<=x;l=r+1)
{
r=x/(x/l);
res+=1ll*(x/l)*(r-l+1)*(l+r);
}
return (1ll*x*x-res/2)%mod;
}
int SqrSum(int x)
{
int a=x+1,b=2*x+1,c=x;
if(x&1)a>>=1;
else c>>=1;
if(x%3==1)b/=3;
else if(x%3==2)a/=3;
else c/=3;
return 1ll*a*b%mod*c%mod;
}
int Calc2(long long x,long long y)
{
long long res=0,lim=min(n,m);
for(int l=1,r;l<=lim;l=r+1)
{
r=min(x/(x/l),y/(y/l));
res+=(x/l)*(y/l)%mod*(SqrSum(r)-SqrSum(l-1))%mod;
res-=1ll*(r-l+1)*(l+r)/2%mod*(x*(y/l)%mod+y*(x/l)%mod)%mod;
}
return (x*y%mod*lim+res)%mod;
}
int main()
{
scanf("%d%d",&n,&m);
printf("%d\n",(1ll*Calc1(n)*Calc1(m)-Calc2(n,m)+mod)%mod);
return 0;
}