P1587 [NOI2016]循环之美

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 7.7k | 阅读时长 ≈ 7 分钟

P1587 [NOI2016]循环之美

传送门

洛谷

题目描述

牛牛是一个热爱算法设计的高中生。在他设计的算法中，常常会使用带小数的数进行计算。牛牛认为，如果在 $k$ 进制下，一个数的小数部分是纯循环的，那么它就是美的。现在，牛牛想知道：对于已知的十进制数 $n$ 和 $m$，在 $k$ 进制下，有多少个数值上互不相等的纯循环小数，可以用分数 $\frac xy$ 表示,其中 $1≤x≤n,1≤y≤m$，且 $x,y$是整数。一个数是纯循环的，当且仅当其可以写成以下形式：
$a.\dot{c_1} c_2 c_3 \dots c_{p - 1} \dot{c_p}$
其中，$a$ 是一个整数，$p≥1$；对于 $1≤i≤p$，$c_i$ 是 $k$ 进制下的一位数字。
例如，在十进制下，$0.45454545……=0.\dot {4} \dot {5}$是纯循环的，它可以用 $\frac {5}{11}$、$\frac{10}{22}$ 等分数表示；在十进制下，$0.1666666……=0.1\dot6$则不是纯循环的，它可以用 $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$

输出格式

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

输入输出样例

输入样例#1：

2 6 10

输出样例#1：

4

说明/提示

满足条件的数分别是：

$\frac{1}{1}=1.0000……$
$\frac{1}{3}=0.3333……$
$\frac{2}{1}=2.0000……$
$\frac{2}{3}=0.6666……$

$\frac{1}{1}$ 和 $\frac{2}{2}$ 虽然都是纯循环小数，但因为它们相等，因此只计数一次；同样，$\frac{1}{3}$ 和 $\frac{2}{6}$ 也只计数一次。

对于所有的测试点，保证 $1 \le n \le 10^9, 1 \le m \le 10^9, 2 \le k \le 2000$。对于每个测试点，有以下约束（其中留空的表示没有特殊的约束）：

测试点编号 $n$ $m$ $k$
$1$ $\leq 10$ $\le 20$ $=2$
$2$ $\leq 100$ $\le 10^4$ $=2$
$3$ $\leq 1000$ $=2$
$4$ $\leq 10000$ $=2$
$5$ $\leq 10$ $\le 20$ $=3$
$6$ $\leq 100$ $\le 10^4$ $=3$
$7$ $\leq 1000$ $=3$
$8$ $\leq 10000$ $=3$
$9$ $\leq 10$ $\le 20$ $\le 100$
$10$ $\leq 100$ $\le 10^4$ $\le 100$
$11$ $\leq 1000$ $\le 1000$
$12$ $\leq 10000$
$13$ $\leq 10^5$ $\le 10^8$ $\le 100$
$14$ $\leq 2 \times 10^5$ $\le 1000$
$15$ $\leq 5 \times 10^5$
$16$ $\leq 10^6$ $\le 10^8$ $\le 100$
$17$ $\leq 2 \times 10^6$ $\le 1000$
$18$ $\leq 5 \times 10^6$
$19$ $\leq 10^7$ $\le 10^8$ $\le 100$
$20$ $\leq 2 \times 10^7$ $\le 1000$
$21$ $\leq 2 \times 10^7$
$22$ $\leq 10^8$ $\le 10^8$
$23$ $\leq 10^8$ $\le 10^8$
$24$
$25$

这部分将提供一个将分数化为对应的小数的方法，如果你已经熟悉这个方法，你不必阅读本提示。

分数可以通过除法，用分子除以分母化为对应的小数。有些分数在除法过程中无法除尽,这样的分数在不断进行的除法过程中余数一定会重复出现。从商数的个位所对应的余数起，设第一次重复出现的余数前两次出现的位置所对应的商数位分别是小数点后第 $a$ 位和小数点后第 $b$ 位（特殊地：如果其中一个对应的商数位是个位，则认为 $a=0$；不妨设 $a<b$），则其循环部分可以用小数点后第 $a+1$ 位到小数点后第 $b$ 位的循环来表示。

例如：在十进制下，将 $\frac{5}{11}$ 转化为小数时，个位开始的商数依次为 $4$,$5$,$4$,…，对应的余数分别为 $6$,$5$,$6$,…。余数第一次重复出现的位置是个位和小数点后第 $2$ 位,那么 $a=0$,$b=2$

$a=0$,$b=2$即其循环部分可以用小数点第 $1$ 位到第 $3$ 位来表示。表示为：$\frac{5}{11}=0.45454545…=0.\dot{4}\dot{5}$。

在十进制下，将 $\frac{1}{6}$ 转化为小数时,个位开始的商数依次为 $1$,$6$,$6$,…，对应的余数分别为 $4$,$4$,$4$,…。余数第一次重复出现的位置是小数点后第 $1$ 位和小数点后第 $2$ 位,即其循环部分可以用小数点后第 $2$ 位来表示。表示为：$\frac{1}{6}=0.1666……=0.1\dot{6}$。

需要注意的是：商数重复出现并不代表进入了循环节。

分析

首先我们假设对于最简分数$\frac{x}{y}$，它的循环节的长度为$s$。（方括号表示取小数部分。）
那么我们将小数点向后移动$s$的倍数为，它小数部分应该不变。
如：十进制下$0.\dot{5}2\dot{0}$，移动$3$位后的$520.\dot{5}2\dot{0}$小数部分一样。
那么我们用式子表示$k$进制下的上述结论：（为了方便，我们只移动移动$s$位。）

由于上文我们已经要求$\frac{x}{y}$是最简分数，即$gcd(x,y)=1$。

即对于最简分数$\frac{x}{y}$，如果它是一个纯循环小数，那么它满足$gcd(k,y)=1$。
枚举分母与分子。
那么答案就是

改变枚举顺序。

莫比乌斯反演一下。

我们设函数

即让$g(x)$表示第一个$\sum$后的一部分式子，让$f(x)$表示第二个$\sum$后的式子。
现在考虑怎么求$f(x)$和$g(x)$。
对于$f(x)$，我们考虑对$1$到$x$的所有数以每$k$个数为一段进行分段，那么就分成了：
$\sum_{i=1}^k[gcd(i,j)=1]$，$\sum_{i=k+1}^{2k}[gcd(i,j)=1]$…
显然上述每段的值相同因为对于每一个数，对于除第一段以外的其他段中的每个数，都可以看作$i+j \times k ( i \le k)$，而$gcd(i+j \times k,k)=gcd(i,j)$，所以除第一段以外的其他段的值都与第一段相同，且均为$f(k)$（定义）。
但是我们不一定能恰好分完，即$x \%k \ne 0$。
可能会剩下$\sum_{i=j \times k+1}^x[gcd(i,k)=1]$。
根据$gcd(i,j)=gcd(i+j \times k,k)$。

我们可以分成$\lfloor \frac{x}{k} \rfloor$个整段。
所以

$k$只有$2000$，可以直接暴力预处理出来。
现在我们再考虑$g(x,k)$

这个式子不好求，所以我们需要再次莫比乌斯反演一下（QAQ）。

额，好像又化不动了。
不过，可以发现如果$gcd(i,j) \ne 1$，那么$\mu(i \times j)=0$，因为有了平方因子。
所以，继续化式子。

于是$g(x,k)$可以递归求。
边界条件$k=1$。
当$k=1$时

此时我们求$\mu(i)$的前缀和，上杜教筛即可。
现在，$f(x)$和$g(x)$都求出来了。
但答案里还有一项 $\lfloor \frac{n}{d} \rfloor$以及边界条件$\lfloor \frac{m}{d} \rfloor$。
这个我们直接二维整除分块就行了。
复杂度$O($能过$)$。

代码

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
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
#define maxk 2010
#define lim 215445
template <typename T>inline T read()
{
    register T sum=0;
    char cc=getchar();
    int sym=1;
    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();
    if(cc=='-')sym=-1,cc=getchar();
    sum=sum*10+cc-'0';
    cc=getchar();
    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();
    return sym*sum;
}
template <typename T>inline T read(T &a)
{
    a=read<T>();
    return a;
}
template <typename T,typename... Others> inline void read(T& a, Others&... b)
{
    a=read(a);
    read(b...);
}
int n,m,K,f[maxk],mu[lim+10],prim[lim+10],sum[lim+10];
long long ans;
map<int,int>mp;
map<pair<int,int>,long long>g;
void init()
{
	mu[1]=1; 
	for(int i=2;i<=lim;i++)
	{
		if(!prim[i])
		{
			prim[++prim[0]]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=prim[0]&&prim[j]*i<=lim;j++)
		{
			prim[prim[j]*i]=true;
			if(i%prim[j]==0)break;
			mu[prim[j]*i]=-mu[i];
		}
	}
	for(int i=1;i<=lim;i++)sum[i]=sum[i-1]+mu[i];
}
int Get(int n)
{
	if(n<=lim)return sum[n];
	if(mp[n])return mp[n];
	int ans=1;
	for(int l=2,r;l<=n;l=r+1)
	{
		r=n/(n/l);
		ans-=(r-l+1)*Get(n/l);
	}
	return mp[n]=ans;
}
long long G(int x,int k)
{
	if(x==0)return 0;
	if(k==1)return Get(x);
	if(g[make_pair(x,k)])return g[make_pair(x,k)];
	long long ans=0;
	for(int i=1;i*i<=k;i++)
		if(k%i==0)
		{
			if(mu[i])ans+=G(x/i,i);
			if(i*i!=k&&mu[k/i])ans+=G(x/(k/i),(k/i));
		}
	return g[make_pair(x,k)]=ans;
}
int F(int x)
{
	return (x/K)*f[K]+f[x%K];
}
int gcd(int a,int b)
{
	return b? gcd(b,a%b):a;
}
int main()
{
	init();
	read(n,m,K);
	for(int i=1;i<=K;i++)
		f[i]=f[i-1]+(gcd(i,K)==1);
	long long ls=0;
	for(int l=1,r;l<=min(n,m);l=r+1)
	{
		r=min(n/(n/l),m/(m/l));
		long long t=G(r,K);
		ans+=(n/l)*(t-ls)*F(m/l);
		ls=t;
	}
	printf("%lld\n",ans);
    return 0;
}