BZOJ 3529 数表

发表于 | 更新于

Link

Solution

定义F(i)F(i)为ii的约数和，则F(i)F(i)可以O(nlogn)O(n\log n)求出。Po姐的代码好象是线性筛？？OTZ。 要求的是

嗯，先不考虑>a>a的限制。 考虑每个数字xx作为gcd\gcd对答案的贡献。有

P(x)=F(x)×c(x)P(x)=F(x)\times c(x)

其中c(x)c(x)为gcd(i,j)==x\gcd(i,j)==x的对数。 而

c(x)=∑x∣dμ(dx)[nd][md]c(x)=\sum_{x|d}\mu(\dfrac dx)[\dfrac nd][\dfrac md]

于是，

Ans=∑xP(x)=∑x{F(x)∑x∣dμ(dx)[nd][md]}Ans=\sum_x P(x)=\sum_x \{F(x)\sum_{x|d}\mu(\dfrac dx)[\dfrac nd][\dfrac md]\}

又见熟悉的分块加速项，把求和式改成枚举dd，则

Ans=∑d[nd][md]∑x∣dF(x)μ(dx)Ans=\sum_d [\dfrac nd][\dfrac md]\sum_{x|d}F(x)\mu(\dfrac dx)

后面的项是可以暴力前缀和的。 有了aa的限制，就需要让所有>a>a的F(i)F(i)不被算进去。于是就用树状数组，动态地加入F(i)F(i)。为了保证复杂度，把询问离线，按照aa排序，然后依次处理，可以保证修改树状数组的复杂度为O(nlogn)O(n\log n)

Tips

对2的整次幂取模，可以用&。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
//Code by Lucida
#include<bits/stdc++.h>
#define red(x) scanf("%d",&x)
//#define debug(x) std::cout<<#x<<'='<<x<<std::endl
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int N=1e5,MAXN=N+10;
typedef long long LL;
using std::pair;
using std::sort;
using std::swap;
using std::min;

pair<int,int> F[MAXN],*curF;
int mu[MAXN],prime[MAXN],pcnt;
void Shake()
{
	static bool notp[MAXN];
	mu[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!notp[i])
			prime[++pcnt]=i,mu[i]=-1;
		for(int j=1;j<=pcnt && prime[j]*i<=N;j++)
		{
			notp[prime[j]*i]=1;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			else
				mu[i*prime[j]]=-mu[i];
		}
	}
	for(int i=1;i<=N;i++)
	{
		F[i].second=i;
		for(int j=i;j<=N;j+=i)
			F[j].first+=i;
	}
	sort(F+1,F+1+N);F[N+1].first=2e9;
	curF=F+1;
}
struct BIT
{
	#define lowbit(x) (x & -x)
	int a[MAXN];
	int sum(int pos)
	{
		if(!pos) return 0;
		int res=0;
		for(;pos;pos-=lowbit(pos))
			res+=a[pos];
		return res;
	}
	int sum(int l,int r){return sum(r)-sum(l-1);}
	void add(int pos,int v)
	{
		if(!pos) assert(1);
		for(;pos<=N;pos+=lowbit(pos))
			a[pos]+=v;
	}
	#undef lowbit
}bit;
void Add(pair<int,int> *p)
{
	for(int i=p->second;i<=N;i+=p->second)
		bit.add(i,p->first*mu[i/p->second]);
}
int Calc(int n,int m)
{
	int res=0;
	if(n>m) swap(n,m);
	for(int i=1,last;i<=n;i=last+1)//+=..
	{
		last=min(n/(n/i),m/(m/i));
		res+=bit.sum(i,last)*(n/i)*(m/i);
	}
	return res;
}
struct Opt
{
	int n,m,a,id;
	bool operator <(const Opt &x) const{return a<x.a;}
}opt[MAXN];
int main()
{
	freopen("input","r",stdin);
	Shake();
	static int ANS[MAXN];
	int T;red(T);
	for(int i=1;i<=T;i++)
	{
		red(opt[i].n),red(opt[i].m),red(opt[i].a);
		opt[i].id=i;
	}
	sort(opt+1,opt+1+T);
	for(int i=1;i<=T;++i)
	{
		while(curF->first<=opt[i].a)
			Add(curF++);
		ANS[opt[i].id]=Calc(opt[i].n,opt[i].m)&0x7FFFFFFF;
	}
	for(int i=1;i<=T;i++) printf("%d\n",ANS[i]);
	return 0;
}