151 lines
4.6 KiB
Markdown
151 lines
4.6 KiB
Markdown
##[$AcWing$ $1291$. 轻拍牛头](https://www.acwing.com/problem/content/description/1293/)
|
||
|
||
### 一、题目描述
|
||
|
||
今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏．
|
||
|
||
贝茜让 $N$ 头奶牛（编号 $1$ 到 $N$）坐成一个圈。
|
||
|
||
除了 $1$ 号与 $N$ 号奶牛外，$i$ 号奶牛与 $i−1$ 号和 $i+1$ 号奶牛相邻，$N$ 号奶牛与 $1$ 号奶牛相邻。
|
||
|
||
农夫约翰用很多纸条装满了一个桶，每一张纸条中包含一个 $1$ 到 $1000000$ 之间的数字。
|
||
|
||
接着每一头奶牛 $i$ 从桶中取出一张纸条，纸条上的数字用 $A_i$ 表示。
|
||
|
||
所有奶牛都选取完毕后，每头奶牛轮流走上一圈，当走到一头奶牛身旁时，如果自己手中的数字能够被该奶牛手中的数字整除，则拍打该牛的头。
|
||
|
||
牛们希望你帮助他们确定，**每一头奶牛需要拍打的牛的数量**。
|
||
|
||
即共有 $N$ 个整数 $A_1,A_2,…,A_N$，对于每一个数 $A_i$，求其他的数中有多少个是它的约数。
|
||
|
||
**输入格式**
|
||
第一行包含整数 $N$。
|
||
|
||
接下来 $N$ 行，每行包含一个整数 $A_i$。
|
||
|
||
**输出格式**
|
||
共 $N$ 行，第 $i$ 行的数字为第 $i$ 头牛需要拍打的牛的数量。
|
||
|
||
**数据范围**
|
||
$1≤N≤10^5,1≤A_i≤10^6$
|
||
|
||
**输入样例：**
|
||
```cpp {.line-numbers}
|
||
5
|
||
2
|
||
1
|
||
2
|
||
3
|
||
4
|
||
```
|
||
**输出样例：**
|
||
```cpp {.line-numbers}
|
||
2
|
||
0
|
||
2
|
||
1
|
||
3
|
||
```
|
||
|
||
|
||
### 二、约数问题三个重要性质
|
||
|
||
#### 1、约数个数
|
||
约数：$1\sim n$中能整除$n$的数字个数。
|
||
|
||
根据唯一分解定理：
|
||
形如:$N=P_1^{c_1} \times P_2^{c_2} \times P_3^{c_3} \times ... \times P_k^{c_k}$
|
||
其中$P_i$为质数因子，$c_i$为此质数因子出现的次数，则约数个数:
|
||
$$f(N)=(c_1+1)\times (c_2+1) \times (c_3+1) \times .... \times (c_k+1)$$
|
||
|
||
也就是所有质数因子的个数$+1$ 再相乘！
|
||
|
||
举个栗子：
|
||
$N=12=2^2 \times 3^1$
|
||
那么$f(N)=(2+1) \times (1+1)=6$,就是有$6$个约数。
|
||
|
||
用手枚举一下：$1,2,3,4,6,12$，共$6$个，与公式计算一致！
|
||
|
||
|
||
**证明**：
|
||
这是一个简单的组合数学公式，以$P_1$为例，它可以选择$0,1,2,...$个，共$C_1+1$种选择方法，每个质数因子都是这样，所以得证。
|
||
|
||
#### 2、$1 \sim N$中，所有数字约数个数和是什么级别？
|
||
$$ \sum_{i=1}^{N}f(i)=\frac{N}{1}+\frac{N}{2}+\frac{N}{3}+...++\frac{N}{N}$$
|
||
这就是一个$O(N*ln(N))$级别的数，非常少~
|
||
|
||
#### 3、整数范围内，约数个数最多的是多少个？
|
||
<font color='red'><b>$0<=N<=2*10^9$,最多有$1600$个，不是很大。</b></font>相比于$\sqrt{N}=50000$要小的太多了.
|
||
|
||
### 三、题目解析
|
||
|
||
如果直接用暴力解法，逐个判断其他的数是不是它的约数，这样时间复杂度是$O(n^2)$，数据规模是$10^5$，会超时
|
||
|
||
**暴力解法** $O(N^2)$
|
||
```cpp {.line-numbers}
|
||
#include <cstdio>
|
||
using namespace std;
|
||
const int N = 1e6 + 10;
|
||
int a[N];
|
||
int n;
|
||
|
||
int main() {
|
||
scanf("%d", &n);
|
||
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
|
||
|
||
for (int i = 0; i < n; i++) {
|
||
int cnt = 0;
|
||
for (int j = 0; j < n; j++)
|
||
if (a[i] % a[j] == 0) cnt++;
|
||
|
||
printf("%d\n", cnt - 1);
|
||
}
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
正着走不行，就只能反着走~
|
||
|
||
假设$i$是$j$的约数，那么$j$就是$i$的倍数。
|
||
|
||
约数和倍数其实是一对 <font color='red' size=4><b>好基友</b></font>，当求约数的时间复杂度过大时，不妨从它倍数的角度来考虑解决问题。
|
||
|
||
这样处理:当判定某个数$i$时，把此数字的所有整数倍数$j$的约数个数$+1$。
|
||
|
||
**优化**
|
||
考虑到可能会有多个$i$的值是相同的，所以类似于**计数排序**的思想，先统计$i$出现的次数，然后再做上面的操作。
|
||
|
||
|
||
### 四、时间复杂度
|
||
看上去双重循环，实则不然：第一层循环的$N$是跑不了的，第二层没有$N$那么多次，是
|
||
$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+...+\frac{1}{N}$
|
||
也就是调和级数$ln(n)+C$，算法最终就是$Nlog(n)$这个级别，比$O(N^2)$要好的多~
|
||
|
||
### 五、实现代码
|
||
```cpp {.line-numbers}
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
#define endl '\n'
|
||
|
||
const int N = 1e6 + 10, M = 1e5 + 10;
|
||
int cnt[N], a[M], res[N];
|
||
int n;
|
||
|
||
int main() {
|
||
// 加快读入
|
||
ios::sync_with_stdio(false), cin.tie(0);
|
||
cin >> n;
|
||
for (int i = 0; i < n; i++) {
|
||
cin >> a[i];
|
||
cnt[a[i]]++;
|
||
}
|
||
|
||
for (int i = 1; i < N; i++) {
|
||
if (!cnt[i]) continue;
|
||
for (int j = i; j < N; j += i) res[j] += cnt[i];
|
||
}
|
||
for (int i = 0; i < n; i++) cout << res[a[i]] - 1 << endl;
|
||
return 0;
|
||
}
|
||
|
||
``` |