【BZOJ2693】jzptab

Time Limit: 5000 ms Memory Limit: 512 MB

description

给你(n, m)，求(sumlimits_{i=1}^{n}sumlimits_{j=1}^{m} lcm(i,j))

答案对100000009取模。

多组数据。

input

第一行有一个正整数tt表示数据组数

接下来tt行每行有两个正整数n,mn,m

output

tt行，第ii行为第ii组询问的答案。

sample input

1
4 5

sample output

HINT

对于100%的数据：(t≤10000,n,m≤10^7)

(100000009)不是一个质数。

solution

做了几题之后感觉。。推起来稍微顺手一点不对顺脑一点了qwq？

（结果这题还是做了很久嗯qwq）

首先还是先写式子咯

[egin{aligned} ans&=sumlimits_{i=1}^{n}sumlimits_{j=1}^{m} lcm(i,j)\ &=sumlimits_{i=1}^{n}sumlimits_{j=1}^{m}frac{ij}{gcd(i,j)}&（抱歉lcm你长得太丑了）\ &=sumlimits_{k=1}^{min(n,m)}ksumlimits_{i=1}^{lfloorfrac{n}{k} floor}sumlimits_{j=1}^{lfloorfrac{m}{k} floor}ij[gcd(i,j)=1]\ \ &这里的话稍微说明一下，我们枚举i和j的gcd（记为k）\&然后原来的i可以表示为i_0*k，原来的j表示为j_0*k，\&frac{ij}{gcd(i,j)}就变成了i_0*j_0*k，所以就变成了上面那样\ \ &=sumlimits_{k=1}^{min(n,m)}ksumlimits_{i=1}^{lfloorfrac{n}{k} floor}sumlimits_{j=1}^{lfloorfrac{m}{k} floor}ijsumlimits_{d|i,d|j}mu(d)&(sumlimits_{d|gcd(i,j)}mu(d)=[gcd(i,j)=1])\ &=sumlimits_{k=1}^{min(n,m)}ksumlimits_{d=1}^{min(lfloor frac{n}{k} floor,lfloor frac{m}{k} floor)}mu(d)sumlimits_{i=1}^{lfloor frac{n}{k} floor}i[dmid i]sumlimits_{j=1}^{lfloor frac{m}{k} floor}j[dmid j]\ \ &观察一下sumlimits_{i=1}^{lfloor frac{n}{k} floor}i[dmid i]，会发现其实这个式子求的就是1到lfloor frac{n}{k} floor范围内d的倍数的和\ \ &=sumlimits_{k=1}^{min(n,m)}ksumlimits_{d=1}^{min(lfloor frac{n}{k} floor,lfloor frac{m}{k} floor)}mu(d) (sum(lfloor frac{n}{kd} floor)d)(sum(lfloor frac{m}{kd} floor)d)&(sum(n)=sumlimits_{i=1}{n}=frac{n(n+1)}{2})\ &=sumlimits_{T=1}^{min(n,m)}sum(lfloor frac{n}{T} floor)sum(lfloor frac{m}{T} floor)sumlimits_{dmid T}mu(d)d^2 frac{T}{d}&(T = kd) end{aligned} ]

化到这一步，我们发现前面的(sum)的部分可以直接分块根号搞定（bzoj2820）

后面的东西看起来十分眼熟啊，我们令(g(x)=sumlimits_{dmid x}mu(d)d^2 frac{x}{d})，令(f(x)=sumlimits_{d|x}d^2mu(d))，令(h(x)=x)

那么(g(x) = sumlimits_{dmid x}f(d)h(frac{x}{d}))，然后由于(f(d))和(h(frac{x}{d}))都是积性函数，所以(g(x))也是积性函数

考虑怎么求(g(x))

我们考虑把这个东西筛出来，按着线性筛的思路来分析一下，求解(g(x))的值

如果说(x)为质数，那么显然(g(x) = x - x^2)

如果(x)不为质数，我们设(x = i * p)，其中(p)为质数，那么有两种情况

(p mid i) ，由于(i)和(p)互质而(g(x))为积性函数，(g(x) = g(i*p) = g(i) * g(p))
(pmid i)，这个时候就有点。。不是很好搞了。。

我们可以把(i)表示为(t * p^k)（(t)与(p)互质）

那么我们就尝试一下从乘了一个(p)会有什么影响这个方面来考虑一下

考虑(g(p^k))的值，显然根据(mu)的定义，只有(mu(1))和(mu(p))能够提供贡献（其他的(p)的指数都>1，所以都是0）

那么我们就可以得到(g(p^k) = f(1)p^{k} + f(p)p^{k-1})

然后写出(g(p^{k+1}))的表达式，会发现是(f(1)p^{k+1} + f(p)p^{k})

也就是说(g(p^{k+1}) = g(p^k) p)

那么就可以得到(g(x) = g(i * p) = g(t * p^k *p) = g(t) * g(p^{k}) * p = g(x) * p)

然后就可以顺利筛出来啦

那这题好像就十分愉快地做完了ovo

#include<iostream>
#include<cstdio>
#include<cstring>
#define MOD 100000009
#define ll long long
using namespace std;
const int MAXN=1e7+10;
ll p[MAXN],g[MAXN],s[MAXN];
bool vis[MAXN];
int ans;
int n,m,T,pos,tmp;
int prework(int n);

int main(){
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	scanf("%d",&T);
	prework(10000000);
	for (int o=1;o<=T;++o){
		scanf("%d%d",&n,&m);
		if (n>m) swap(n,m);
		pos=ans=0;
		for (int i=1;i<=n;i=pos+1){
			pos=min(n/(n/i),m/(m/i));
			ll tmp=(s[n/i]*s[m/i]%MOD*(g[pos]-g[i-1])%MOD)%MOD;
			ans=((ll)ans+tmp+MOD)%MOD;
		}
		printf("%d
",ans);
	}
}

int prework(int n){
	g[1]=1; s[1]=1;
	int cnt=0;
	memset(vis,false,sizeof(vis));
	for (int i=2;i<=n;++i){
		s[i]=(ll)i*(i+1)/2%MOD;
		if (!vis[i]){
			g[i]=(i-(ll)i*i%MOD+MOD)%MOD;
			p[++cnt]=i;
		}
		for (int j=1;j<=cnt&&i*p[j]<=n;++j){
			vis[i*p[j]]=true;
			if (i%p[j])
				g[i*p[j]]=g[i]*g[p[j]]%MOD;
			else{
				g[i*p[j]]=g[i]*p[j]%MOD;
				break;
			}
		}
	}
	for (int i=1;i<=n;++i)
		g[i]=(g[i]+g[i-1])%MOD;
}