[Usaco2008 Dec]Patting Heads

It's Bessie's birthday and time for party games! Bessie has instructed the N (1 <= N <= 100,000) cows conveniently numbered 1..N to sit in a circle (so that cow i [except at the ends] sits next to cows i-1 and i+1; cow N sits next to cow 1). Meanwhile, Farmer John fills a barrel with one billion slips of paper, each containing some integer in the range 1..1,000,000. Each cow i then draws a number A_i (1 <= A_i <= 1,000,000) (which is not necessarily unique, of course) from the giant barrel. Taking turns, each cow i then takes a walk around the circle and pats the heads of all other cows j such that her number A_i is exactly divisible by cow j's number A_j; she then sits again back in her original position. The cows would like you to help them determine, for each cow, the number of other cows she should pat.

題目大意就是
給出n個數，然後對每個數，求出其他的數有幾個是它的約數

數的范圍是到100W
然後n的范圍是10W

不能直接n^2暴力求

不過可以使用一種類似於篩法的方法。

 #include <iostream>  
#include <cstdio>  
#include <algorithm>  
using namespace std; 
int a[1111111]; 
int num[1111111]; 
int n, nt; 
int x[111111]; 
int t[111111]; 
void ready() 
{ 
    for(int i = 0; i < nt; i++) 
        for(int j = x[i]; j <= 1000000; j += x[i]) 
            a[j] += num[x[i]]; 
} 
int main() 
{ 
    scanf("%d", &n); 
    for(int i = 0; i < n; i++) 
        scanf("%d", &x[i]), t[i] = x[i], num[x[i]]++; 
    sort(x, x + n); 
    nt = unique(x, x + n) - x; 
    ready(); 
    for(int i = 0; i < n; i++) printf("%d\n", a[t[i]] - 1); 
    return 0; 
}