轻拍牛头
题目 轻拍牛头
今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏．
贝茜让 N 头奶牛（编号 1 到 N）坐成一个圈。
除了 1 号与 N 号奶牛外，i 号奶牛与 i−1 号和 i+1 号奶牛相邻，N 号奶牛与 1 号奶牛相邻。
农夫约翰用很多纸条装满了一个桶，每一张纸条中包含一个 到 1000000 之间的数字。
接着每一头奶牛 从桶中取出一张纸条，纸条上的数字用 Ai 表示。
所有奶牛都选取完毕后，每头奶牛轮流走上一圈，当走到一头奶牛身旁时，如果自己手中的数字能够被该奶牛手中的数字整除，则拍打该牛的头。
牛们希望你帮助他们确定，每一头奶牛需要拍打的牛的数量。
输入格式
第一行包含整数 N。
接下来 N 行，每行包含一个整数 Ai。
输出格式
共 N 行，第 i 行的数字为第 i 头牛需要拍打的牛的数量。
数据范围
\(1≤N≤10^5, 1≤Ai≤10^6\)输入样例：
5 2 1 2 3 4
输出样例：
2 0 2 1 3
思路分析
即共有 N 个整数 A1,A2,…,AN 对于每一个数 Ai，求其他的数中有多少个是它的约数。
直接写法是 把这些数都存起来 然后枚举每个数 再来一层枚举 判断除它外的每个数是否能被它整除
两层for循环 时间复杂度是O(n2)的，肯定会TLE
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int cows[N],beat[N];
int n;
int main()
{
cin>>n;
for(int i=0;i<n;i++)
cin>>cows[i];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(cows[i]%cows[j]==0)
beat[i]++;
}
cout<<beat[i]-1<<endl;
}
return 0;
}
考虑优化
如果存在一个数x，那么\(2×x,3×x⋯⌊max_num/x⌋×x\)都是x的倍数，所以那些牛都会拍x的头
如果 b 是 a 的倍数，那么 b 可以被 a 整除。基于这个概念，我们可以将问题转化为对于每个数 ai，计算有多少个数是它的倍数，从而确定每头牛需要拍打的牛的数量。这种方法避免了直接比较每对数是否互相整除的 O(n2) 复杂度，而是通过统计倍数关系来实现更高效的计算。
- 统计每个数的出现次数：首先，我们需要知道每个数 ai 出现的次数，因为如果有多头牛拿着相同的数字，那么拍打次数会相应增加。
- 计算倍数的累积：对于每个数 ai，遍历其所有可能的倍数 j=ai,2ai,3ai,… 直到上限 M。对于每个倍数
j，其实就是在说：所有能被 ai 整除的 j 都会对 ai 产生一次拍打。因此，我们将 ai 的出现次数累加到所有 j 的计数上。这样做的结果是
ans[j]表示所有能整除 j 的 ai 的总出现次数。 - 输出结果：最后，对于每个数 ai，其需要拍打的牛的数量就是
ans[ai] - 1（减去1是因为不能拍打自己）。
\(O(nlogM)\)，其中 M 是数的上限（在本题中为$ 10^6$）。这得益于对每个数 ai，我们只需要遍历其倍数进行计数，而不需要对每对数进行直接的整除判断。
这个倍数的思想出现好几次了 前面阶乘分解也是 2出现多少次 再看2的倍数出现多少次 累加起来就是2出现多少次
细想一下好像就这么回事
原本加在一起算的话 2 4 8 积为64 其中2出现6次 实际上就是2占的1次加4占的2次加8占的3次
又是类似于分治的思想 把问题拆分成小问题进行求解
这是对于质数来说的
对于约数其实也一样啊
如果b是a的倍数 那么b的倍数一定也是a的倍数
那也可以用这种拆开算各部分的数量进行累加的方式得到总数量
能敲打我这头牛的（我的倍数） 一定可以敲打我能敲打的牛 又有点像dp的状态转移了 从已知状态推出后续状态 用cnt记录每头牛能敲打的数量 更新它的时候同时把它的倍数给更新掉（用上面的演示 就相当于给4和8累加上第一轮2 碰到4时 又是给8累加上第二轮2……）这样分开计算累加到ans[i]里 最终的结果ans[i]保存的就是第i头牛总的可敲打数
（暴力思路从每头牛能敲打谁入手 这个思路反过来 从每头牛能被哪些牛敲打 累计起来为总敲打数）
chatgpt:
确实，这种倍数思想在很多算法中都很常见，特别是在处理整数的除法和倍数关系时。它利用了数论中的基本概念来优化算法，减少不必要的计算，以实现高效的解决方案。
对于阶乘分解问题，我们不需要真正计算出阶乘的值，而是直接计算质数在阶乘中出现的次数。对于每个质数 p，我们可以通过除以 p，p2，直到 pk（其中 pk≤n）来计算 p 在 n! 中出现的次数。这个过程称为质因数的幂次累加。
对于轻拍牛头问题，我们可以采用类似的思路。如果我们知道每个数的出现次数，我们可以遍历每个数 ai，并累加它的所有倍数的出现次数。这样，对于每个倍数 j，我们可以更新一个累加计数器，来统计能整除 j 的所有数的总出现次数。换句话说，我们可以通过计算每个数的倍数来反向累加它们将会拍打的牛的次数。
核心是计算每头奶牛需要拍打的牛的数量。对于每个数，它会累加所有倍数的出现次数。这个过程就像是一个简单的动态规划（DP）或者说是状态转移的过程。最终，每头奶牛的答案保存在 ans 数组中，输出时减去自身，得到需要拍打的牛的数量。
- 暴力方法：
- 对于每头奶牛，枚举其它所有奶牛，检查自己的数字是否能被其他奶牛的数字整除。
- 如果能整除，拍打次数加一。
- 时间复杂度为 O(N2)，因为需要对每对奶牛进行一次整除判断。
- 优化的方法（基于倍数关系）：
- 统计每个数字出现的次数。
- 对于每个数字 i，遍历它的所有倍数 j，然后将 i 出现的次数累加到 j 的拍打次数上。
- 这意味着，如果数字 i 出现了 c 次，那么所有 i 的倍数都会至少被拍打 c 次（由数字 i 导致的拍打）。
- 时间复杂度为 O(NlogM)，其中 M 是数字的最大值。这是因为对于每个数 i，其倍数的遍历次数近似于 logi。
暴力方法直接计算每头牛能拍打谁，而优化方法则是计算每头牛能被哪些牛拍打，并累计这些次数来得到总拍打次数。优化方法的确是将问题反过来考虑，通过反向关系来统计结果。这种思路在算法中很常见，特别是在整数除法和倍数的问题中，能够将时间复杂度从平方级别降低到线性对数级别。
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10; // 数组大小限制
const int M = 1e6 + 10; // 数字的最大值限制
int cows[N]; // 存储每头奶牛手中的数字
int cnt[M]; // 统计每个数字出现的次数
int ans[M]; // 存储每个数字需要拍打的次数
int n;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> cows[i];
cnt[cows[i]]++; // 统计每个数字出现的次数
}
// 对每个出现的数字，累加其倍数的约数数量
for (int i = 1; i < M; i++) {
if (cnt[i]) { // 如果数字i出现过
for (int j = i; j < M; j += i) {
ans[j] += cnt[i]; // 累加倍数的约数数量
}
}
}
// 输出每头奶牛需要拍打的次数，不包括自己
for (int i = 0; i < n; i++) {
cout << ans[cows[i]] - 1 << endl;
}
return 0;
}
同类题型
视频讲解
⬅️ 试除法求约数 🏠 00-刷题理模型 ➡️ （可能要放在拓展欧几里得里）GCD
💬 评论