简单莫反板子求调
查看原帖
简单莫反板子求调
613794
jianhe楼主2024/9/17 14:20

rt,样例过了但是 WA 0pt。

#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll N=1e7,mod=20101009;
ll T,n,m,ct,mu[N+1],p[N+1];
bitset<N+1> vis;
void init(){
	mu[1]=1;
	for(int i=2;i<=n;i++){
		if(!vis[i]) p[++ct]=i,mu[i]=-1;
		for(int j=1;j<=ct&&i*p[j]<=n;j++){
			vis[i*p[j]]=1;
			if(!(i%p[j])){mu[i*p[j]]=0;break;}
			mu[i*p[j]]=-mu[i];
		}
	}
	for(int i=2;i<=m;i++) mu[i]=((mu[i]*i%mod*i%mod+mu[i-1])%mod+mod)%mod;
}
ll g(ll n,ll m){return (n+1)*n/2%mod*((m+1)*m/2%mod)%mod;}
ll f(ll n,ll m){
	ll res=0;
	if(n>m) n^=m^=n^=m; 
	for(ll l=1,r;l<=n;l=r+1)
		r=min(n/(n/l),m/(m/l)),res+=(mu[r]-mu[l-1]+mod)%mod*g(n/l,m/l)%mod,res%=mod;
	return res;
}
ll calc(ll n,ll m){
	ll res=0;
	for(ll l=1,r;l<=n;l=r+1)
		r=min(n/(n/l),m/(m/l)),res+=(l+r)*(r-l+1)/2%mod*f(n/l,m/l)%mod,res%=mod;
	return res;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;if(n>m) n^=m^=n^=m;
	init();cout<<calc(n,m);
	return 0;
}
2024/9/17 14:20
加载中...