TOJ 3349 Counting Divisor / 素数筛选法

Counting Divisor 时间限制(普通/Java):1000MS/3000MS 运行内存限制:65536KByte

If an integer A can divide integer B exactly, then A can be called a divisor of B.

Now there are N (1 <= N <= 100,000) integesr, for each of these number, please count the number of divisor from the rest N-1 integers.

The first line of input data is an integer N, the following N rows have a positive integer,and each integer isn't above 1,000,000。

According to the input order output every integer in the rest N - 1 integer number of divisor.

#include <stdio.h>#include <string.h>#include <algorithm>#include <math.h>using namespace std;int cnt[1000010];int map[1000010];int a[100010];int main(){int n,i,j,max = 0;scanf("%d",&n);for(i = 1;i <= n; i++){scanf("%d",&a[i]);cnt[a[i]]++;if(max < a[i])max = a[i];}for(i = 1;i <= max; i++){if(cnt[i]){for(j = i + i; j <= max; j += i)//和素数筛选差不多 赞一个 {map[j] += cnt[i];}}}for(i = 1;i <= n; i++){if(cnt[a[i]] > 1)printf("%d\n",map[a[i]] + cnt[a[i]] - 1);elseprintf("%d\n",map[a[i]]);}return 0;}