HDU 5212 Code

筛法。

统计所有 [数] 的所有 [倍数] 的 [数] 的个数，即 i 的所有倍数 i, 2i, 3i, 4i...个数为 dp[i]，

则所有倍数两两结合共有 dp[i] * dp[i] 个。

此处覆盖 dp[i] = dp[i] * dp[i]。

对于新的 dp[i] 数组，从后往前逆推，设已完成的子问题 d[j] 为 j 作为 [最大公约数] 的所有数对的个数。

因为 dp[i] 是所有以 i 为 [公约数] 的数对个数，dp[i] 去掉 [ i 是公约数] 但 [ i 不是最大公约数] 的那些数对的个数（即所有的 [ j 是 i 的倍数 ] 的d[j]）则得到 d[i]（代码中相当于 d[i] 覆盖 dp[i]）。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 typedef long long LL;
 5 int dp[11111];
 6 int num[11111];
 7 int sum[11111];
 8 int n;
 9 int main()
10 {
11     while(scanf("%d", &n) != EOF)
12     {
13         int maxnum = 0, ans = 0;
14         memset(sum, 0, sizeof(sum));
15         for(int i = 0; i < n; i ++)
16         {
17             scanf("%d", &num[i]);
18             sum[num[i]] ++;
19             maxnum = maxnum < num[i] ? num[i] : maxnum;
20         }
21         memset(dp, 0, sizeof(dp));
22         for(int i = 2; i <= maxnum; i ++)
23         {
24 
25             for(int j = i; j <= maxnum; j += i)
26             {
27                 dp[i] += sum[j];
28             }
29             dp[i] *= dp[i];
30         }
31         for(int i = maxnum; i >= 2; i --)
32         {
33             for(int j = i + i; j <= maxnum; j += i)
34                 dp[i] -= dp[j];
35             ans = (ans + (LL)i * (i - 1) * dp[i]) % 10007;
36         }
37         printf("%d
", ans);
38     }
39     return 0;
40 }