题目描述

今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏．

贝茜让 N 头奶牛（编号 1 到 N）坐成一个圈。

除了 1 号与 N 号奶牛外，i 号奶牛与 i−1 号和 i+1 号奶牛相邻，N 号奶牛与 1 号奶牛相邻。

农夫约翰用很多纸条装满了一个桶，每一张纸条中包含一个 1 到 1000000 之间的数字。

接着每一头奶牛 i 从桶中取出一张纸条，纸条上的数字用 Ai 表示。

所有奶牛都选取完毕后，每头奶牛轮流走上一圈，当走到一头奶牛身旁时，如果自己手中的数字能够被该奶牛手中的数字整除，则拍打该牛的头。

牛们希望你帮助他们确定，每一头奶牛需要拍打的牛的数量。

即共有 N 个整数 A1,A2,…,AN，对于每一个数 Ai，求其他的数中有多少个是它的约数。

输入格式
第一行包含整数 N。

接下来 N 行，每行包含一个整数 Ai。

输出格式
共 N 行，第 i 行的数字为第 i 头牛需要拍打的牛的数量。

数据范围
$1≤N≤10^5$,
$1≤A_i≤10^6$

样例

输入
5
2
1
2
3
4
输出
2
0
2
1
3

算法 倍数法

这题如果暴力求解时间复杂度为$O(n^2)$，依次枚举每个数是否是当前数的约数，不可取。可以反过来考虑，对于每个数d，在1~N中以d为约数的数就是d的倍数，d,d*2,d*3...,N/d*d。因此可以从小到大枚举每个约数，将约数统计到这个约数的倍数对应的数上去。倍数法求一个数的约数个数的代码如下：

for(int i=0;i<n;i++){
        cin >> a[i] ;
        cnt[a[i]] ++ ; //表示存在该约数
    }


    for(int i=1;i<M;i++){
        for(int j=i;j<M;j+=i){
            s[j] += cnt[i] ;  // 记录好每个约数的倍数对应的约数个数
        }
    }

上述算法的时间复杂度是$O(N+N/2+N/3+…N/N) = O(NlogN)$

时间复杂度 $O(NlogN)$

C++ 代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std ;

const int N = 100010, M = 1000010 ;

int a[N],cnt[M],s[M] ;
int n ; 

int main(){
    cin >> n ;

    for(int i=0;i<n;i++){
        cin >> a[i] ;
        cnt[a[i]] ++ ;
    }


    for(int i=1;i<M;i++){
        for(int j=i;j<M;j+=i){
            s[j] += cnt[i] ;
        }
    }
    for(int i=0;i<n;i++){
        cout << s[a[i]] - 1 << endl ;
    }
    return 0 ;
}