P1587 [NOI2016]循环之美

NOI2016D1T3~~反正是T几都无所谓了啊~~

题意:求 $\sum_{x=1}^n\sum_{y=1}^m\frac{x}{y}$
在 $k$ 进制下能表示成循环节从第一位小数开始的无限循环小数或整数的最简分数个数

首先硬点循环节长度l

所以$$[\frac{xk^l}{y}]=[\frac{x}{y}]$$
[]表示一个数小数部分

这是什么意思呢?相当于在K进制下把小数部分提前l位之后的数的小数部分还是相同的.可以结合十进制 $10^l$ 理解

\frac{x*k^l}{y}-\lfloor {\frac{x*k^l}{y}} \rfloor=\frac{x}{y}-\lfloor {\frac{x}{y}} \rfloor

同时乘y并对y取模

x*k^l \equiv x(mod y)

题目只考虑最简分数 $(x,y)=1$

k^l \equiv 1(mod y)

这个显然就是k和y互质了

Ans=\sum_{i=1}^{m}\sum_{j=1}^m[(i,j)==1][(j,k)==1]

这个神仙东西前一个[]和后一个[]都是可以处理的,可以看
题解区第一篇神仙的

这里处理第一个,就是 $[(i,j)==1]$

交换求和顺序

=\sum_{j=1}^m[(j,k)==1]\sum_{i=1}^{m}[(i,j)==1]

莫比乌斯反演展开

=\sum_{j=1}^m[(j,k)==1]\sum_{i=1}^{m}\sum_{d|i,d|j}\mu{d}

d再到最前面

=\sum_{d=1}^n\mu{d}\sum_{d|i}^n\sum_{d|j}^m[(j,k)==1]

把枚举他的倍数变成枚举他的几倍

=\sum_{d=1}^n[d ⊥ k]\mu{d}\sum_{i=1}^{n/d}\sum_{j=1}^{m/d}[gcd(j,k)==1]

(因为j,k要互质d,k要先互质才行)
有个循环没用

=\sum_{d=1}^n[d ⊥ k]\mu{d}\lfloor\frac{n}{d}\rfloor\sum_{j=1}^{m/d}[gcd(j,k)==1]

好我们可以分成两个了

f(x)=\sum_{i=1}^x[(i,k)==1]

S(x)=\sum_{i=1}^x[i⊥k]\mu{i}

考虑f(x)怎么做

相当于每k段他的答案是一样的

所以 $f(x)=\lfloor\frac{x}{k}\rfloor f(k)+f(x%k)$
k<=2000,只需要预处理就可以O1了

问题在于S(x)

设 $S(x,k)=\sum_{i=1}^x[i⊥k]\mu{i}$

=\sum_{i=1}^x\mu{i}[(i,k)==1]

=\sum_{i=1}^x\mu{i}\sum_{d|i,d|k}\mu{d}

=\sum_{d|k}\mu{d}\sum_{d|i}\mu{i}

=\sum_{d|k}\mu{d}\sum_{i=1}^{x/d}\mu{id}

$(i,d)!=1$ 则 $\mu(id)=0$ 不会对答案造成影响

$\therefore (i,d)==1$

=\sum_{d|k}\mu(d)\sum_{i=1,i⊥d}^{x/d}\mu(i)\mu(d)

=\sum_{d|k}\mu(d)^2\sum_{i=1,i⊥d}^{x/d}\mu(i)

=\sum_{d|k}\mu(d)^2\sum_{i=1}^{x/d}\mu(i)[i⊥d]

=\sum_{d|k}\mu(d)^2S(\lfloor \frac{x}{d} \rfloor,d)

直接模拟这个式子是错的,不是T掉,是k=1时无法继续递归

于是我们把k=1带入 $S(x,1)=\sum_{i=1}^x\mu(i)$

这个不是杜教筛?

所以做完了a

复杂度是 $O((k的质因子个数)\sqrt n+n^{\frac{2}{3}})$

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
const int MAXN=1e7;
#define ll long long
namespace fastIO {
#define BUF_SIZE (1<<19)
	static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
	inline char nc() {
		if(p1==pend) {
			p1=buf;
			pend=buf+fread(buf,1,BUF_SIZE,stdin);
		}
		return *p1++;
	}
	inline int read() {
		int x=0,f=1;
		register char s=nc();
		for(; !isdigit(s); s=nc())if(s=='-')f=-1;
		for(; isdigit(s); s=nc())x=(x<<1)+(x<<3)+s-'0';
		return x*f;
	}
}
using namespace fastIO;
int n,K,N,m;
bool pp[5000];
int F[5000];
bool zs[MAXN+10];
int tot,pri[MAXN+1],mu[MAXN+1],smu[MAXN+2];
map<pair<int,int>,int> M;
void pre() {
	for(int i=1; i<=K; ++i)pp[i]=__gcd(i,K)==1;
	for(int i=1; i<=K; ++i)F[i]=F[i-1]+pp[i];
	//F数组预处理
	zs[1]=1;
	mu[1]=1;
	for(int i=2; i<=N; ++i) {
		if(!zs[i])pri[++tot]=i,mu[i]=-1;
		for(int j=1; j<=tot&&i*pri[j]<=N; ++j) {
			zs[i*pri[j]]=1;
			if(i%pri[j])mu[i*pri[j]]=-mu[i];
			else break;
		}
	}
	//杜教筛预处理
	for(int i=1; i<=N; ++i)smu[i]=smu[i-1]+mu[i];
}

int SF(int x) {
	return (x/K)*F[K]+F[x%K];
	//O1算出F数组
}

int SS(int x,int k) {
	if((k==1&&x<=N)||(!x))return smu[x];
	//已经进入杜教筛了
	if(M[make_pair(x,k)])return M[make_pair(x,k)];
	//记搜返回
	int ret=0;
	if(k==1) {
		ret=1;//\mu*1=υ 
		for(int i=2,j; i<=x; i=j+1) {
			j=x/(x/i);
			ret-=(j-i+1)*SS(x/i,1);
			//整除分块杜教筛
		}
		//整除分块
	} else {
		for(int i=1; i*i<=k; ++i) {
			if(k%i==0) {
				if(mu[i])ret+=SS(x/i,i);
				if(i*i!=k&&mu[k/i])ret+=SS(x/(k/i),k/i);
			} 
			//根号n枚举约数 
		}
	}
	return M[make_pair(x,k)]=ret;
}

int main() {
	scanf("%d%d%d",&n,&m,&K);
	N=MAXN;
	pre();
	ll ans=0,lt=0,nw=0;
	for(int i=1,j; i<=min(n,m); i=j+1) {
		j=min(n/(n/i),m/(m/i));
		nw=SS(j,K);
		ans+=1ll*(nw-lt)*(n/i)*SF(m/i);//只有n/i单独算了 
		lt=nw;
		//整除分块
	}
	printf("%lld\n",ans);
	return 0;
}

夏晓光(loveJY)的博客

P1712 [NOI2016]区间