BZOJ 2956 模积和分块

2956: 模积和

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1192 Solved: 536
[Submit][Status][Discuss]

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。

HINT

Source

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

思路：参考博客 http://blog.csdn.net/u012288458/article/details/51010847

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 19940417
ll sum(ll k)//n*(n+1)/2
{
 return k*(k+1)/2%MOD;
}
ll sum2(ll k)//n*(n+1)*(2*n+1)/6
{
 return k*(k+1)%(6*MOD)*(2*k+1)%(6*MOD)/6%MOD;
}
ll cal(ll k)
{
 ll res=k*k%MOD;
 ll next;
 for(ll i=1;i<=k;i=next+1)
 {
  next=k/(k/i);
  ll temp=(k/i)*(sum(next)-sum(i-1)+MOD)%MOD;
  res=(res-temp+MOD)%MOD;
 }
 return res;
}
int main()
{
 ll n,m;
 scanf("%lld %lld",&n,&m);
 if(n>m)swap(n,m);
 ll ans=cal(n)*cal(m)%MOD;
 ll next;
 for(ll i=1;i<=n;i=next+1)
 {
  next=min(n/(n/i),m/(m/i));
  ll num1=n*m%MOD*(next-i+1)%MOD;
  ll num2=(n/i*m+m/i*n)%MOD*(sum(next)-sum(i-1)+MOD)%MOD;
  ll num3=(n/i)*(m/i)%MOD*(sum2(next)-sum2(i-1)+MOD)%MOD;
  ans=(ans-(num1-num2+num3)%MOD+MOD)%MOD;
 }
 printf("%lld\n",ans);
 return 0;
}

BZOJ 2956 模积和 分块