Description

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

贝茜让 \(n\) 头奶牛坐成一个圈. 除了 \(1\) 号与 \(n\) 号奶牛外,\(i\) 号奶牛与 \(i-1\) 号和 \(i+1\) 号奶牛相邻.\(n\) 号奶牛与 \(1\) 号奶牛相邻. 农夫约翰用很多纸条装满了一个桶, 每一张包含了一个独一无二的 \(1\) 到 \(1000000\) 的数字.

接着每一头奶牛 \(i\) 从柄中取出一张纸条 \(a_i\) ．每头奶牛轮流走上一圈, 同时拍打所有 编号能整除在纸条上的数字的牛的头, 然后做回到原来的位置. 牛们希望你帮助他们确定, 每一头奶牛需要拍打的牛.

Input

第 \(1\) 行包含一个整数 \(n\), 接下来第 \(2\) 到 \(n+1\) 行每行包含一个整数 \(a_i\).

Output

第 \(1\) 到 \(n\) 行, 每行的输出表示第 \(i\) 头奶牛要拍打的牛数量.

Sample Input

5
2
1
2
3
4

Sample Output

2
0
2
1
3

Data Range

对于所有的数据, 满足:\(1 \leq n \leq 100000\)

Explanation

题意: 求有 \(n\) 个数, 每一个数是 \(n\) 个数中 (除自己外) 多少个数的约数.

由于最大数不超过 \(10^6\), 所以可以建一个布尔数组. 然后对于每一个数, 若其存在, 则每一个它的倍数都加上它的值. 注意这个操作的复杂度是 \(O(m \sqrt{m})\) 的, 其中 \(m = max\{a_i, 1 \leq i \leq n\}\).

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int maxn = 1000100;

int n, maxx;
int a[maxn], cnt[maxn], sm[maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        cnt[a[i]] += 1;
        maxx = max(maxx, a[i]);
    }
    for (int i = 1; i <= maxx; i++) if (cnt[i] > 0)
        for (int j = i; j <= maxx; j += i)
            sm[j] += cnt[i];
    // Output
    for (int i = 1; i <= n; i++)
        printf("%d\n", sm[a[i]] - 1);
    return 0;
}