P1587 [NOI2016] 循环之美 题解

P1587 [NOI2016] 循环之美

这道题我推到后面推不下去了，最后还是看了题解。还是切不了这种题唉。

前置知识：杜教筛

开始时看不出什么，我们先用经验和手玩来找一下规律。

我们考虑 \(K=10\) 的情况。根据我们的经验，如果 \(\dfrac 1y\) 是纯循环的，那么它的任意整数倍也应当是纯循环的。发现 \(y\) 可以为 \(1,3,7,9,11,13,\cdots\)。

我们不由得猜测，当且仅当 \(y\perp K\) 时，\(\dfrac 1y\) 是纯循环的。

尝试证明一下。首先证明第一个结论。如果 \(\dfrac 1y\) 是一个纯循环小数，\(\dfrac xy\) 则是这个小数乘以 \(x\) 的结果。可以将循环节的每一位乘以 \(x\) 累加到结果中。每一个循环节都是同样的结果，接受后面的进位也都相同。若进位到整数部分也不影响小数部分纯循环。

第二个结论的证明采用反证法。假设存在一个 \(y\) 使得 \(\gcd(y,K)>1\) 且 \(\dfrac 1y\) 是纯循环小数，根据第一个结论，其正整数倍数也是纯循环小数。如果 \(K\) 是 \(y\) 的倍数，显然 \(\dfrac 1y\) 是一个有限小数，矛盾。否则，设 \(z=\gcd(y,K)\)，则 \(\dfrac 1y\) 可以表示为一个有限小数 \(\dfrac 1z\) 与一个纯循环小数 \(\dfrac zy\) 的乘积。一个有限小数又可以表示为 \(\sum a_iK^i(0\le a_i<K,i<0)\) 的形式。如果一个纯循环小数乘以 \(K^k\)（\(k\) 是任意负整数），相当于在 \(K\) 进制下这个小数左移了 \(|k|\) 位，小数点后会多 \(k\) 个零。由于循环节是非零的，这样势必打破循环。乘以 \(\sum a_iK^i\) 也同理。于是这样的 \(y\) 不存在。

于是得出结论：如果没有 \(y\perp K\)，那么 \(\dfrac xy\) 不是纯循环的。第二个结论是其逆否命题，自然成立。

其实，在上面的证明过程中，\(\dfrac zy\) 仍然是一个纯循环小数。因为 \(\gcd(\dfrac yz,K)=1\)。

但是，在 \(\gcd(y,K)>1\) 时， \(\dfrac xy\) 也有可能是纯循环的。不过从第二个结论的证明过程中可以看出，若把 \(\dfrac 1y\) 表示为一个有限小数与一个纯循环小数的乘积，则 \(\dfrac xy\) 出现纯循环的情况，一定是 \(x\) 乘以那个有限小数得到了一个整数的结果。即，\(\dfrac{xz}y\) 是正整数。所以 \(\gcd(x,y)>1\)，\(\dfrac xy\) 一定不是最简的。

因此我们得出结论：一个最简分数 \(\dfrac xy\) 在 \(K\) 进制下是纯循环的，当且仅当 \(y\perp K\)。

所以题目就是要我们求：

为使用数论分块，我们将这个式子除去 \(\lfloor\frac nd\rfloor\) 后拆成两个函数。

设 \(\mathbf f(n)=\sum_{i=1}^n[i\perp K]\)，即从 \(1\) 到 \(n\) 中与 \(K\) 互质的数的个数。对于一个数 \(x\)，根据欧几里得定理，\(\gcd(x,K)=\gcd(K,x\bmod K)\)，所以 \(x\perp K\iff x\bmod K\perp K\)。故 \(\mathbf f(n)=\lfloor\frac nK\rfloor\sum_{i=1}^K[i\perp K]+\mathbf f(n\bmod K)=\lfloor\frac nK\rfloor\varphi(K)+\mathbf f(n\bmod K)\)。所以最终有

设 \(\mathbf g(n,k)=\sum_{i=1}^n\mu(i)[i\perp k]\)。

好像推不下去了，我们可以想办法搞一个递推出来。

即 \(\mathbf g(n,k)=\sum_{d\mid k}\mu(d)^2\mathbf g(\lfloor\frac nd\rfloor,d)=\sum_{d\mid k}[\mu(d)\ne 0]\mathbf g(\lfloor\frac nd\rfloor,d)\)。

边界：\(\mathbf g(0,k)=0,\mathbf g(n,1)=\sum_{i=1}^n\mu(i)\)。后一个可以使用杜教筛。

于是对于原式

的相等的一块 \(d\in[l,r]\)，答案为

下面分析用大写字母表示输入。

具体实现用杜教筛时我没有手写哈希，因为传入参数可能是 \(\lfloor\dfrac Nx\rfloor\) 也可能是 \(\lfloor\dfrac Mx\rfloor\)，学习笔记里提到的哈希函数不可用，我也没有找到合适的哈希函数。所以直接用了 unordered_map。

\(\mathbf g(n,k)\) 中的 \(k\) 显然只可能是 \(K\) 的因数，在 \(2000\) 以内的数中因数最多的为 \(1680\)，只有 \(40\) 个（可以写一个暴力算出来），而 \(n\) 只可能是 \(\lfloor\dfrac Nx\rfloor\) 或者 \(\lfloor\dfrac Mx\rfloor\)，最多只有 \(2\sqrt N+2\sqrt M\) 种取值（并且远远不会达到这个上界），所以状态只有 \(\mathcal O(\mathbf d(K)(\sqrt N+\sqrt M))\) 种，假设 \(N,M\) 同级，时间复杂度为 \(\mathcal O(K\log K+\mathbf d(K)\sqrt N+N^{\frac 23})\)，可以通过。

代码如下。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
typedef long long ll;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
const int N=1e6,MK=2e3+5,sN=3.2e4,MAXN=1e9+1;
ll H(int n,int k){return (ll)MAXN*k+n;}
int K,v[N+1],mu[N+1],f[MK],S[N+1];
vector<int>pr;unordered_map<ll,int>g;
inline void init(){
	for(int i=1;i<=K;i++)f[i]=f[i-1]+(gcd(K,i)==1?1:0);
	S[1]=mu[1]=1;for(int i=2;i<=N;i++){
		if(!v[i])pr.push_back(v[i]=i),mu[i]=-1;
		for(int p:pr){
			if(p>v[i]||p>N/i)break;
			v[i*p]=p;
			if(p==v[i])break;
			mu[i*p]=-mu[i];
		}
		S[i]=S[i-1]+mu[i];
	}
}
inline int F(int n){
	return (n/K)*f[K]+f[n%K];}
int G(int n,int k){
	if(!n)return 0;
	ll p=H(n,k);if(g[p])return g[p];
	if(k==1){
		if(n<=N)return g[p]=S[n];
		int ret=1;for(int l=2,r;l<=n;l=r+1){
			r=n/(n/l);ret-=G(n/l,1)*(r-l+1);
		}
		return g[p]=ret;
	}
	int ret=0;
	for(int d=1;d*d<=k;d++){
		if(k%d)continue;
		if(mu[d])ret+=G(n/d,d);
		if(((d*d)^k)&&mu[k/d])ret+=G(n/(k/d),k/d);
	}
	return g[p]=ret;
}
int main(){
	int n,m,mn;scanf("%d%d%d",&n,&m,&K);
	init();ll ans=0;mn=min(n,m);
	for(int l=1,r,x1,x2=0;l<=mn;l=r+1){
		r=min(n/(n/l),m/(m/l));x1=G(r,K);
		ans+=(ll)(x1-x2)*(n/l)*F(m/l);x2=x1;
	}
	printf("%lld\n",ans);
	return 0;
}

原文地址：http://www.cnblogs.com/hihihi198/p/16882085.html