自动搬运

查看原文

来自洛谷，原作者为

	syksykCCC 相信并抓住那些源于热爱，忠于自我的每一个可能性

搬运于2025-08-24 22:22:10，当前版本为作者最后更新于2020-06-03 00:37:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

zrm 哥哥自己不写 sol 做 ppt 差评 /kel

好，那么官方题解只能我来写了 /kk

十进制有限小数

什么样子的分数可以表示为十进制有限小数？

约分后，分母只含 $2, 5$ 两种因子的分数可以。

感性证明：

写成十进制有限小数的充要条件显然是分数可以通分为 $\frac{a}{100\dots}$ 的形式，也就是对于一个整数左移小数点。

而形如 $10^x$ 的数必然 $=2^x\times 5^x$，所以，分母只含 $2, 5$ 两个因子即可。

子任务 1：$n \le 10^3$

做法 1

显然，枚举 $p$，枚举 $q$，暴力约分，判断 $q$ 约分后是不是只含 $2, 5$ 两种因子是可行的。

枚举的时间复杂度为 $O(n^2)$，约分的时间复杂度为 $O(\log n)$，判断分母的时间复杂度也为 $O(\log n)$，后面两者并列，所以，时间复杂度为 $O(n^2 log n)$。

至此，你还没有当年的小 Z 厉害（

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n, ans = 0;
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		for(int j = 1; j <= n; j++)
		{
			int p = i, q = j;
			int g = __gcd(p, q);
			p /= g; q /= g;
			while(q % 2 == 0) q /= 2;
			while(q % 5 == 0) q /= 5;
			if(q == 1) ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

做法 2

把分数分解一下，可以写为以下的形式：

$$\frac{bc}{ac}$$

$a$ 本身只含 $2, 5$ 两种因子，$c$ 本身不含 $2, 5$ 两种因子（也就是把分母需要约分的部分拆出来），$b$ 为任意数，显然，这样的分数都是合法的，而且任何合法的分数都是这种形式。

那么，依次在 $[1, n]$ 范围枚举 $a$（合法的 $a$ 的表可以预处理）在 $[1, \lfloor\frac{n}{a} \rfloor]$ 范围枚举合法的 $c$，在 $[1, \lfloor\frac{n}{c} \rfloor]$ 的范围内枚举 $b$，每枚举到一次就把答案加 $1$，时间复杂度 $O(n^2)$。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, x[100000], cnt, ans;
signed main()
{
	cin >> n;
	for(int i = 1; i <= n; i *= 2)
		for(int j = i; j <= n; j *= 5)
			x[++cnt] = j;
	sort(x + 1, x + cnt + 1);
	for(int i = 1; i <= cnt; i++)
	{
		int a = x[i];
		for(int b = 1; a * b <= n; b++)
		{
			if(b % 2 == 0 || b % 5 == 0) continue;
			for(int c = 1; b * c <= n; c++)
			{
				ans++;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

子任务 2：$n \le 10^7$

被极短的 $O(n \log n)$ 切了，长见识了 qwq

做法 1

观察上一个做法，发现不知道最后一重循环在干啥 /发抖

也就是说，枚举完一组 $a$ 和 $c$ 后，它对答案的贡献就是分子所能取的数量，即 $[1, \lfloor\frac{n}{c} \rfloor]$，直接加上这个贡献就好了。

那么省掉了一重循环，因为分母的枚举是 $n$ 个不重不漏，时间复杂度 $O(n)$。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, x[100000], cnt, ans;
signed main()
{
	cin >> n;
	for(int i = 1; i <= n; i *= 2)
		for(int j = i; j <= n; j *= 5)
			x[++cnt] = j;
	sort(x + 1, x + cnt + 1);
	for(int i = 1; i <= cnt; i++)
	{
		int a = x[i];
		for(int b = 1; a * b <= n; b++)
		{
			if(b % 2 == 0 || b % 5 == 0) continue;
			ans += n / b;
		}
	}
	cout << ans << endl;
	return 0;
}

做法 2

想要继续优化，发现很难了，回到 $O(n^2 )$ 的做法，能不能通过转换顺序来达到优化时间的目的呢？

$$\frac{bc}{ac}$$

尝试先枚举 $c$，那么，$b$ 的取值依然是 $[1, \lfloor\frac{n}{c} \rfloor]$ 的任何数，而 $a$ 的取值就变为了 $[1, \lfloor\frac{n}{c} \rfloor]$ 中任何只含 $2, 5$ 两种因子的数，发现，$a$ 的取值的个数随着 $c$ 的增大而单调减小，所以可以在总共 $O(n)$ 的时间中计算，也就是，对于每个 $c$，记合法的 $a$ 的个数为 $d$，则它对答案的贡献为 $d \times \lfloor\frac{n}{c} \rfloor$。

时间复杂度依然是 $O(n)$。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, x[100000], cnt, ans;
signed main()
{
	cin >> n;
	for(int i = 1; i <= n; i *= 2)
		for(int j = i; j <= n; j *= 5)
			x[++cnt] = j;
	sort(x + 1, x + cnt + 1);
	int a = cnt;
	for(int b = 1; b <= n; b++) 
	{
		if(b % 2 == 0 || b % 5 == 0) continue; 
		while(a && x[a] > n / b) a--;
		ans += a * (n / b);
	}
	cout << ans << endl;
	return 0;
}

子任务 3：$n \le 10^{12}$

不妨把 $d$ 写的更直接一点，换成 $f(x)$，表示 $[1, x]$ 中只含 $2, 5$ 两个因子的数的个数。前面那个式子等价于：

$$f\left(\left\lfloor\frac{n}{c} \right\rfloor\right)\times\left\lfloor\frac{n}{c} \right\rfloor $$

发现，这个是一种经典的整除分块形式，直接整除分块，可以把时间复杂度加速到 $O(\sqrt{n})$。

真的这么简单么？

别忘了，$c$ 的取值并不是 $[1, n]$ 当中的每一个数，而是不含 $2, 5$ 因子的数。

之前枚举的是 $c$，所以可以直接判断 $c \bmod 2$ 和 $c \bmod 5$ 是不是为 $0$，但现在我们要整段的处理 $c$，怎么办呢？

先忽略这个限制，把 $c$ 的取值范围当作 $[1, n]$ 当中的每一个数处理。比如 $c\in[l, r]$ 时贡献相同，就可以通过容斥计算出 $[l,r ]$ 中实际的合法的 $c$ 的个数。

$$e= g([l, r], 1)-g([l, r], 2)-g([l, r], 5)+g([l, r], 10) $$

$g([l, r], x)$ 表示 $[l, r]$ 中 $x$ 的倍数的个数，可以类似前缀和得到。（即 $g([1, r], x) - g([1, l], x)$，左端点为 $1$ 显然除一除就好了）

那么，这一段的贡献就是 $e\times f\left(\left\lfloor\frac{n}{c} \right\rfloor\right)\times\left\lfloor\frac{n}{c} \right\rfloor$，时间复杂度 $O(\sqrt{n})$。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, x[100000], cnt, ans;
signed main()
{
	cin >> n;
	for(int i = 1; i <= n; i *= 2)
		for(int j = i; j <= n; j *= 5)
			x[++cnt] = j;
	sort(x + 1, x + cnt + 1);
	int a = cnt;
	for(int l = 1, r; l <= n; l = r + 1)
	{
		int t = n / l;
		r = t == 0 ? n : n / t;
		while(a && x[a] > t) a--;
		int valid = r - l + 1;
		valid -= r / 2 - (l - 1) / 2;
		valid -= r / 5 - (l - 1) / 5;
		valid += r / 10 - (l - 1) / 10;
		ans += valid * a * t; 
	}
	cout << ans << endl;
	return 0;
}

水一句：比神花还短（（光速逃