银联高校极客挑战赛 初赛 第二场 B码队弟弟的求和问题(除法分块)

Lianjie

化简一下公式：
$p=10^9+7$p=109+7
${\sum }_{i=1}^n{\sum }_{j=1}^m\left(ij\left(n\%i\right)\left(m\%j\right)\right)\%p$∑i=1n​∑j=1m​(ij(n%i)(m%j))%p

$={\sum }_{i=1}^{n}i\left(n\%i\right){\sum }_{j=1}^m\left(j\left(m\%j\right)\right)\%p$=∑i=1n​i(n%i)∑j=1m​(j(m%j))%p
$={\sum }_{i=1}^{n}i\ast (n-\lfloor \frac{n}{i}\rfloor \ast i){\sum }_{j=1}^{m}j\ast (m-\lfloor \frac{m}{j}\rfloor \ast j)\%p$=∑i=1n​i∗(n−⌊in​⌋∗i)∑j=1m​j∗(m−⌊jm​⌋∗j)%p
$={\sum }_{i=1}^n(i\ast n-\lfloor \frac{n}{i}\rfloor \ast i^2){\sum }_{j=1}^m(j\ast m-\lfloor \frac{m}{j}\rfloor \ast j^2)\%p$=∑i=1n​(i∗n−⌊in​⌋∗i2)∑j=1m​(j∗m−⌊jm​⌋∗j2)%p

然后直接分块就能做了
细节见代码

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
const LL M=1e9+7;
int n,m;
LL f(int l,int r){
	return (1ll*(l+r)%M*(r-l+1)%M*powmod(2,M-2,M))%M;
}
LL g(int l,int r){
	return (1ll*(r+1)*r%M*(2*r+1)%M*powmod(6,M-2,M)%M-1ll*(l-1)*l%M*(2*l-1)%M*powmod(6,M-2,M)%M+M)%M;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>m;
	int j;
	LL res=0;
	for(int i=1;i<=m;i=j+1){
		j=m/(m/i);
		res+=f(i,j)*m%M;
		res-=g(i,j)*(m/i)%M;
		res+=M;
		res%=M;
	} 
	LL ans=0;
	for(int i=1;i<=n;i=j+1){
		j=n/(n/i);
		LL mid=f(i,j)*n%M;
		mid-=g(i,j)*(n/i)%M;
		mid+=M;
		mid%=M;
		mid*=res;
		mid%=M;
		ans+=mid;
		ans%=M;
	}
	cout<<(ans+M)%M<<endl;
	return 0;
}