题解 P2926 【[USACO08DEC]拍头Patting Heads】

· · 题解

本蒟蒻的一篇题解~~~

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

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

思路分析:首先使用一个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