解法發(fā)現(xiàn)網(wǎng)上一個(gè)大牛寫的很好，就轉(zhuǎn)載過來吧。可憐的我，開始沒想到算法就算了，想到算法后又刻意依賴STL結(jié)果o(N)寫成o(logN)成功葬送。
1 # include <cstdio>
2 # include <map>
3 # include <cstring>
4 # include <algorithm>
5 using namespace std;
6 int pa[2000],pp=0,sa[10],sp=0;
7 int refer[5][10001];
8 void make_prime()
9 {
10 bool used[10001];
11 memset(used,
true,
sizeof(used));
12 for(
int i=2;i<=10000;i++)
13 if(used[i])
14 {
15 pa[pp++]=i;
16 for(
int j=2*i;j<=10000;j+=i)
17 used[j]=
false;
18 }
19 }
20 void spilt(
int n)
21 {
22 sp=0;
23 for(
int i=0;i<pp&&n!=1;i++)
24 if(n%pa[i]==0)
25 {
26 sa[sp++]=pa[i];
27 while(n%pa[i]==0)
28 n/=pa[i];
29 }
30 }
31 void putmap(
int n)
32 {
33 spilt(n);
34 for(
int i=1;i<(1<<sp);i++)
35 {
36 int n1=0,n2=1;
37 for(
int j=0;j<5;j++)
38 if(i&(1<<j))
39 n1++,n2*=sa[j];
40 refer[n1-1][n2]++;
41 }
42 }
43 long long c(
int n)
44 {
45 return (
long long)n*(n-1)*(n-2)*(n-3)/4/3/2;
46 }
47 long long getans(
int n)
48 {
49 long long ans=c(n);
50 for(
int i=0;i<5;i++)
51 {
52 bool flag=
false;
53 for(
int j=1;j<=10000;j++)
54 if(refer[i][j]>=4)
55 flag=
true,
56 ans+=c(refer[i][j])*(i%2?1ll:-1ll);
57 if(!flag)
break;
58 }
59 return ans;
60 }
61 int main()
62 {
63 int n;
64 make_prime();
65 while(scanf("%d",&n)!=EOF)
66 {
67 memset(refer,0,
sizeof(refer));
68 for(
int i=0;i<n;i++)
69 {
70 int t;
71 scanf("%d",&t);
72 putmap(t);
73 }
74 printf("%lld\n",getans(n));
75 }
76 return 0;
77 }