class="markdown_views prism-atom-one-light">
Description
求
∑i=1n∑j=1mnmodi∗mmodj" role="presentation">∑i=1n∑j=1mnmodi∗mmodj其中i!=j
对于100%的数据n,m<=10^9。
Solution
那个i!=j看着很不爽,直接容斥减掉下标相同的,然后拆开来就直接分块求和好了
刷水题都不能1a我真是太弱了
Code
#include
#include
#include
#define rep(i,st,ed) for (int i=st;i<=ed;++i)
typedef long long LL;
const LL ny2=9970209;
const LL ny6=3323403;
const LL MOD=19940417;
LL get1(LL x) {
return x*(x+1)%MOD*ny2%MOD;
}
LL get2(LL x) {
return x*(x+1)%MOD*(2*x%MOD+1)%MOD*ny6%MOD;
}
LL cal1(LL a,LL b) {
return (get1(b)-get1(a-1)+MOD)%MOD;
}
LL cal2(LL a,LL b) {
return (get2(b)-get2(a-1)+MOD)%MOD;
}
void solve(LL n,LL m) {
LL a=n*n%MOD,b=m*m%MOD;
for (LL i=1,j;i<=n;i=j+1) {
j=n/(n/i);
a=(a-(n/i)%MOD*cal1(i,j)%MOD+MOD)%MOD;
}
for (LL i=1,j;i<=m;i=j+1) {
j=m/(m/i);
b=(b-(m/i)%MOD*cal1(i,j)%MOD+MOD)%MOD;
}
LL ans=a*b%MOD;
LL tot=n*m%MOD*n%MOD;
LL tot1=0,tot2=0,tot3=0;
for (LL i=1,j;i<=n;i=j+1) {
j=n/(n/i);
tot2=(tot2+(n/i)%MOD*cal1(i,j)%MOD)%MOD;
}
for (LL i=1,j;i<=n;i=j+1) {
j=std:: min(m/(m/i),n);
tot1=(tot1+(m/i)%MOD*cal1(i,j)%MOD)%MOD;
}
for (LL i=1,j;i<=n;i=j+1) {
j=std:: min(n/(n/i),m/(m/i));
tot3=(tot3+(n/i)%MOD*(m/i)%MOD*cal2(i,j)%MOD)%MOD;
}
tot=((((tot-tot1*n%MOD)+MOD)%MOD-tot2*m%MOD+MOD)%MOD+tot3)%MOD;
ans=(ans-tot+MOD)%MOD;
if (ans<0) ans=(ans+MOD)%MOD;
printf("%lld
", ans);
}
int main(void) {
freopen("data.in","r",stdin);
LL n,m; scanf("%lld%lld",&n,&m);
if (mstd:: swap(n,m);
solve(n,m);
return 0;
}