2017-03-01

【bzoj2693】jzptab

本文为博主原创，未经许可不得转载

AC通道

题解

这题是$bzoj2154$的加强版

由于多组数据，我们像$bzoj2154$那样的$O(n)$做法已经不行了，考虑进一步优化

$ans=\sum_{d=1}^{min(n,m)}d\times F(\left [ \frac{n}{d} \right ],\left [ \frac{m}{d} \right ])=\sum_{d=1}^{min(n,m)}d\sum_{i=1}^{min(n,m)}i^2 \times \mu(i)\times Sum(\left [ \frac{n}{di} \right ],\left [ \frac{m}{di} \right ])=\sum_{D=1}^{min(n,m)}Sum(\left [ \frac{n}{d} \right ],\left [ \frac{m}{d} \right ])\sum_{i|d}^{ }\frac{D}{i}\times i^2\times \mu(i)$

我们发现$\sum_{i|d}^{ }\frac{D}{i}\times i^2\times \mu(i)$可以用前缀和来优化

注意到积性函数的约数和也是积性函数

因此后面的那坨东西可以利用线性筛求出来

线性筛当$i%prime[j]=0$时不满足积性函数的条件，但是由于此时$\mu(prime[j])=0$，故多出来的因数的函数值都是0，增加的只有原先因数的答案乘了个$prime[j]$而已

然后我们就可以$O(\sqrt n)$回答询问了

参考代码

#include<bits/stdc++.h>
#define FILE "read"
using namespace std;
typedef long long ll;
const int MAXN=(int)1e7,D=50,mod=(int)(20101009);
int cnt,check[MAXN+D],prime[MAXN+D];
ll sum[MAXN+D];
namespace INIT{
	char buf[1<<15],*fs,*ft;
	inline char getc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int read(){
		int x=0,f=1;  char ch=getc();
		while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getc();}
		while(isdigit(ch))  {x=x*10+ch-'0';  ch=getc();}
		return x*f;
	}
}using namespace INIT;
void pre(){
	sum[1]=1;
	for(int i=2;i<=MAXN;++i){
		if(!check[i])  prime[++cnt]=i,sum[i]=(i-(ll)i*i)%mod;
		for(int j=1;j<=cnt&&prime[j]*i<=MAXN;++j){
			check[prime[j]*i]=1;
			if(i%prime[j]==0) {sum[i*prime[j]]=(sum[i]*prime[j])%mod; break;}
			sum[i*prime[j]]=(sum[i]*sum[prime[j]])%mod;
		}
	}
	for(int i=2;i<=MAXN;++i)  sum[i]+=sum[i-1]%mod,sum[i]%=mod;
}
inline ll get(ll x,ll y) {return ((x*(x+1)>>1)%mod)*((y*(y+1)>>1)%mod)%mod;}
int solve(int n,int m){
	if(n>m)  swap(n,m);  int ans=0;
	for(int i=1,last;i<=n;i=last+1){
		last=min(n/(n/i),m/(m/i));
		ans+=(sum[last]-sum[i-1])*get(n/i,m/i)%mod;
		ans%=mod;
	}
	printf("%d\n",(ans+mod)%mod);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	pre();
	for(int T=read();T;T--){
		int n=read(),m=read();
		solve(n,m);
	}
	return 0;
}

本文标题:【bzoj2693】jzptab

文章作者:chty

发布时间:2017年03月01日 - 22时03分

最后更新:2018年03月02日 - 17时25分

许可协议:本文为博主原创，未经许可不得转载。