[USACO08DEC]拍头Patting Heads 题解

题目链接：智能手机

题意：N个数字a[i]，求N个数字中除去第i个数字，有多少数字为a[i]的因子？

数据范围：a[i],n<=1e6.

我这里介绍两种方法：

1.枚举x=1--->n，再sqrt(x)的去判断x的因子个数。时间复杂度O(n*sqrt(n)).

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long int
#define R register
using namespace std;
const int N=1e6+10;
int n,a[N],ans[N],num[N],Max;
int main(){
    memset(ans,-1,sizeof(ans));
    scanf("%d",&n);
    for(R int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        Max=max(Max,a[i]);
        ++num[a[i]];
    }
    for(R int i=1;i<=n;++i){
    R int k=a[i];
    for(R int x=1;x<=sqrt(k);++x)
    if(k%x==0){
        R int y=k/x; 
        ans[i]+=num[x]+num[y];
        if(x*x==k)ans[i]-=num[x];
    }
    }
    for(R int i=1;i<=n;++i)
    printf("%d
",ans[i]);
    return 0;
}
// O(n)枚举每个数字 
// O(sqrt(n))枚举 当前数字的 因子 

2.枚举因数，a[i]的因数最大值为max(a[i])(i=1--->n)。再去枚举因数的倍数，最大值为Max/i。已知调和级数可以证明时间复杂度为O(n*log2(n)).

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long int
#define R register
using namespace std;
const int N=1e6+5;
int n,a[N],num[N],ans[N],Max;
int main(){
    memset(ans,-1,sizeof(ans));
    scanf("%d",&n);
    for(R int i=1;i<=n;i++){
    scanf("%d",&a[i]);
    Max=max(Max,a[i]);
    num[a[i]]++;
    }
    for(R int i=1;i<=Max;i++){//枚举因数
    if(!num[i])continue;
    for(R int j=1;j<=Max/i;j++)//枚举因数的倍数
    ans[i*j]+=num[i];
    }
    for(R int i=1;i<=n;i++)    
    printf("%d
",ans[a[i]]);
    return 0;
}
// 枚举 数字
// 用 每个数字 去更新 它的倍数.

因为要删去自己整除自己的情况，所以memset(ans,-1,sizeof(ans)).