「NOI2016」循环之美

发表于
字数统计: 1,331字 | 阅读时长 ≈ 6min

「NOI2016」循环之美

题目描述

牛牛是一个热爱算法设计的高中生。在他设计的算法中，常常会使用带小数的数进行计算。牛牛认为，如果在 $k$ 进制下，一个数的小数部分是纯循环的，那么它就是美的。

现在，牛牛想知道：对于已知的十进制数 $n$ 和 $m$，在 $k$ 进制下，有多少个数值上互不相等的纯循环小数，可以用分数 $\frac x y$ 表示，其中 $1\le x\le n,1\le y\le m$，且 $x,y$ 是整数。

一个数是纯循环的，当且仅当其可以写成以下形式：

其中，$a$ 是一个整数，$p\ge1$；对于 $1\le i\le p$，$c_i$ 是 $k$ 进制下的一位数字。

例如，在十进制下，$0.45454545\dots=0.\dot{4}\dot{5}$ 是纯循环的，它可以用 $\frac 5 {11}$、$\frac{10}{22}$ 等分数表示；在十进制下，$0.1666666\dots=0.1\dot{6}$ 则不是纯循环的，它可以用 $\frac 1 6$ 等分数表示。

需要特别注意的是，我们认为一个整数是纯循环的，因为它的小数部分可以表示成 $0$ 的循环或是 $k-1$ 的循环；而一个小数部分非 $0$ 的有限小数不是纯循环的。

输入格式

输入文件只有一行，包含三个十进制数 $n,m,k$，意义如题所述。

输出格式

只输出一行一个整数，表示满足条件的美的数的个数。

数据范围与提示

对于所有的测试点，保证 $1\le n\le 10^9$，$1\le m\le 10^9$，$2\le k\le2000$。

首先考虑怎样的$x,y(gcd(x,y)=1)$满足$\frac{x}{y}$在$k$进制下是纯循环的。假设$k$进制下循环节为$a$位，那么有$xk^a \equiv x (mod \ y)$。由于$gcd(x,y)=1$，那么有$k^a\equiv 1(mod \ y)$。也就是说，如果$\frac{x}{y}$在$k$进制下是纯循环的，那么这个关于$a$的同余方程一定要有非负整数解，那么有$gcd(k,y)=1$。

那么写出答案式并推导一番：

之后会反复用到这一个式子：

其中$e$是元函数，即$e(n)=[n=1]$。

代入答案式继续推导：

设$N=min(n,m)$。交换枚举顺序，设$y=id$,$x=jd$,先枚举$d$得：

设$f(n)=\sum_{i=1}^n[(i,k)=1]$，那么答案式就是$\sum_{d=1}^N\mu(d)[(d,k)=1]\lfloor \frac{n}{d} \rfloor f(\lfloor \frac{m}{d}\rfloor)$。按照上面提到的式子简化对$f(n)$的计算：

注意到本题中$k$很小，因数个数很少，所以对于$f(n)$可以预处理出$k$的因数，暴力计算。

观察发现$\lfloor \frac{n}{d}\rfloor$和$\lfloor \frac{m}{d}\rfloor$总共只有$O(\sqrt n)$种取值，容易想到分块处理，那么现在的问题就在于求出$g(n,k)=\mu(n)[(n,k)=1]$的前缀和，记$sum(n,k)=\sum_{i=1}^ng(i)$，下面尝试简化对$sum$的运算：

对于$\sum \mu(ie)$的形式，想要利用$\mu$的积性。注意到当$(i,e)=1$时，$\mu(ie)=\mu(i)\mu(e)$；而当$(i,e)>1$时，$\mu(ie)=0$，所以对上式再进行一番推导：

于是现在可以迭代求$sum(n,k)$。注意到每一次迭代要么使$n$减小，要么使$k$减小，考虑迭代的终点：当$n=0$时，答案显然为$0$;当$k=1$时，$sum(n,1)$就是$\mu$的前缀和，此时用杜教筛处理。

时间复杂度？蒟蒻不会算，但是感觉很可过的样子。测一波极限数据，发现真的可过。

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
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#include<unordered_map>
#define ll long long
#define MAXN 1000000
using namespace std;

int N,M,K;ll Ans;
vector<int>fac[2005];
int P[MAXN],mu[MAXN+5],s[MAXN+5];bool mark[MAXN+5];
unordered_map<int,int>sum;
unordered_map<ll,int>g;

void Euler(){
	int i,j;
	s[1]=mu[1]=1;mark[1]=true;
	for(i=2;i<=MAXN;i++){
		if(!mark[i])P[++P[0]]=i,mu[i]=-1;
		for(j=1;j<=P[0]&&i*P[j]<=MAXN;j++){
			mark[i*P[j]]=true;
			if(i%P[j]==0){mu[i*P[j]]=0;break;}
			mu[i*P[j]]=-mu[i];
		}
		s[i]=s[i-1]+mu[i];
	}
}

int getsum(int n){
	if(n<=MAXN)return s[n];
	if(sum.count(n))return sum[n];
	int i,j;ll ret=1;
	for(i=2;i<=n;i=j+1){
		j=n/(n/i);
		ret-=(ll)(j-i+1)*getsum(n/i);
	}
	sum[n]=ret;
	return ret; 
}

ll f(int n){
	ll ret=0;int i,d;
	for(i=0;i<fac[K].size();i++){
		d=fac[K][i];
		ret+=(ll)mu[d]*(n/d);
	}
	return ret;
}

ll calc(int n,int k){
	if(n==0)return 0;
	if(n==1)return 1;
	if(k==1)return getsum(n);
	ll st=(ll)n*(K+1)+k;int i,e,ret=0;
	if(g.count(st))return g[st];
	for(i=0;i<fac[k].size();i++){
		e=fac[k][i];
		if(mu[e]==0)continue;
		ret+=calc(n/e,e);
	}
	g[st]=ret;
	return ret;
}

int main(){
	Euler();
	int i,j,n;ll tmp;
	scanf("%d%d%d",&N,&M,&K);
	
	for(i=1;i<=K;i++)
	for(j=i;j<=K;j+=i)fac[j].push_back(i);
	
	n=min(N,M);
	for(i=1;i<=n;i=j+1){
		j=min(N/(N/i),M/(M/i));
		Ans+=(ll)(N/i)*f(M/i)*(calc(j,K)-calc(i-1,K));
	}

	printf("%lld\n",Ans);
}