「LOJ 2085」「NOI2016」循环之美

发表于

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

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

一个数是纯循环的，当且仅当其可以写成以下形式：a.c1˙c2c3⋯cp−1cp˙a.\dot{c_1}c_2 c_3\cdots c_{p-1}\dot{c_p} 。
​​
其中，aa 是一个整数， p≥1p\ge 1 ；对于 1≤i≤p1\le i\le p ，cic_i 是 kk 进制下的一位数字。

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

Constraints

1≤n,m≤1091\le n,m \le 10^9 ， 2≤k≤20002 \le k \le 2000

Solution

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

例如：在十进制下，将 511\frac{5}{11} 转化为小数时，个位开始的商数依次为 4,5,4,…4, 5, 4, \ldots ，对应的余数分别为 6,5,6,…6, 5, 6, \ldots 。余数第一次重复出现的位置是个位和小数点后第 22 位，那么 a=0,b=2a = 0, b = 2 即其循环部分可以用小数点第 11 位到第 33 位来表示。表示为：511=0.45454545…=0.4˙5˙\frac{5}{11} = 0.45454545 \ldots = 0. \dot{4}\dot{5}。

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

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

由以上提示，我们可以得到一个结论：若循环节长度为 nn ，则 xkn≡x(mody)xk^n\equiv x \pmod y 。又因为相同的数字只计算一次，所以 gcd(x,y)=1gcd(x,y)=1 ，则可得结论 kn≡1(mody)k^n\equiv 1 \pmod y ，即 gcd(k,y)=1gcd(k,y)=1 。

所以可以推导以下公式：

    ∑x=1n∑y=1m[gcd(y,k)=1][gcd(x,y)=1]=∑d=1min(n,m)[gcd(d,k)=1]μ(d)⌊nd⌋∑y=1⌊md⌋[gcd(y,k)=1]\begin{aligned} &~~~~\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(y,k)=1][gcd(x,y)=1] \\ &= \sum_{d=1}^{min(n,m)}[gcd(d,k)=1]\mu (d)\left \lfloor \frac{n}{d} \right \rfloor \sum_{y=1}^{\left \lfloor \frac{m}{d} \right \rfloor}[gcd(y,k)=1]\\ \end{aligned}

令 f(i)=∑y=1i[gcd(y,k)=1]f(i)=\sum_{y=1}^{i}[gcd(y,k)=1] ，则当 i>ki>k 时， f(i)=⌊ik⌋f(k)+f(imodk)f(i)=\left \lfloor \frac{i}{k} \right \rfloor f(k)+f(i\bmod k) 。

可以得到 84 分。

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
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=2e7+5;
const int K=2e3+5;
int n,m,k,mx,cnt;
int f[K],miu[N],pri[N];
LL ans;
bool np[N];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
LL F(int x)
{
	if(x<=k)return f[x];
	return x/k*f[k]+f[x%k];
}
int main()
{
	n=read();m=read();k=read();
	mx=min(n,m);miu[1]=1;
	for(int i=2;i<=mx;i++)
	{
		if(!np[i])miu[i]=-1,pri[++cnt]=i;
		for(int j=1;i*pri[j]<=mx;j++)
		{
			np[i*pri[j]]=true;
			if(i%pri[j]==0){miu[i*pri[j]]=0;break;}
			miu[i*pri[j]]=-miu[i];
		}
	}
	for(int i=1;i<=k;i++)f[i]=f[i-1]+(gcd(i,k)==1);
	for(int i=1;i<=mx;i++)
	{
		if(gcd(i,k)!=1)continue;
		ans+=1ll*miu[i]*(n/i)*F(m/i);
	}
	printf("%lld",ans);
	return 0;
}