自动搬运

查看原文

来自洛谷，原作者为

	zhukewen123 **

搬运于2025-08-24 21:43:30，当前版本为作者最后更新于2018-09-22 23:08:11，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本蒟蒻的一篇题解~~~

由于本题纯暴力枚举会炸的

所以应该采用一种特殊方法

思路分析:首先使用一个b数组来存储奶牛手上数字出现的次数,比如数字是3,那么b[3]++,数字是2,就b[2]++.然后列举奶牛手上的所有数字i,如果他们的倍数j也在b数组中,就用一个cnt数组记录,即cnt[ixj]++,代表有数字i*j的奶牛可以拍手上数字为i的奶牛的头.举个例子,奶牛数字2,4,6,若i是2,那么它的整数倍为j为2,4,6,8,10......发现奶牛有2,4这两个数字,那么cnt[4]++,cnt[6]++.然后i=4,i=6不断往后推即可......最终输出cnt[奶牛数字]即可.

代码如下

#include<bits/stdc++.h>
using namespace std;
int a[10000005];
int n,mx=-100;
int b[10000005];
int cnt[10000005];
void get_factor(){
    for (int i = 1;  i <= 10000000; i++){
    	if(!b[i]) continue;//奶牛数字中必须有i
    	for (int j = 1; j <= 10000000 / i; j++){
    		 if(b[i*j]) cnt[i*j]+=b[i];
    		 if(i*j==i) cnt[i]--;
             //防止奶牛拍自己的头QWQ
        }   	
    } 
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[a[i]]++;
    }
    get_factor();
    for(int i=1;i<=n;i++)
        cout<<cnt[a[i]]<<endl;
    //华华丽丽的输出
} 

求过QWQ~~~

看懂了不要忘了点赞哦QWQ