三元组计数_cf 三元组计数

$$\mathrm{三元组计数}$$

题目链接：$\mathrm{n}\mathrm{o}\mathrm{w}\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{r}213276$

到牛客看：

——>点我跳转<——

题目

牛牛现在有 $n$ 个数分别是 $1,2,3,...,n$，牛牛特别喜欢数三元组，如果三个数 $a,b,c$ 满足 $b$ 是 $a$ 的倍数，$c$ 是 $b$ 的倍数，那么牛牛就觉得这三个数形成的三元组是有趣的。

现在给定 $n$ 的大小，牛牛想知道有多少个三元组 $(a,b,c)$，$a<b<c$ 是有趣的。

输入

一行一个整数 $n$ 表示牛牛现在有 $1,2,3,...,n$ 这些数。

输出

一个整数表示牛牛觉得有趣的三元组的个数。

样例输入

10
1

样例输出

9
1

数据范围

对于 $20\%$ 的数据，$1\le n\le 500$
对于 $40\%$ 的数据，$1\le n\le 1e5$
对于 $100\%$ 的数据，$1\le n\le 1e6$

思路

这道题其实就是一道模拟。

其实我们就是要 $x\times a=b$ 而且 $y\times b=c$。
（$x,y$ 为正整数）

那我们可以先普通枚举 $a$，然后直接从 $a+a$ 开始枚举 $a$ 的倍数作为 $b$，然后再从 $b+b$ 开始枚举 $b$ 的倍数作为 $c$。
那每一次枚举出来的 $(a,b,c)$ 就是一对合法的三元组。

我是用三重循环扫过去，一次一次加的，很明显其实可以优化。
但是也可以过，我就懒得优化了。

代码

#include<cstdio>
#define ll long long

using namespace std;

int n;
ll ans;

int main() {
	scanf("%d", &n);
	
	for (int i = 1; i <= n / 4; i++)//枚举 a
		for (int j = i + i; j <= n / 2; j += i)//对于当前的 a 枚举合法的 b
			for (int k = j + j; k <= n; k += j)//对于当前的 b 枚举合法的 c
				ans++;
	
	printf("%lld", ans);
	
	return 0;
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20