BZOJ 4146 [AMPPZ2014] Divisors 解题报告

这个题感觉比较小清新。。。

我们记录每个数出现的次数 $T_i$。

首先依次枚举每个数字，令 $ans = ans + T_i imes (T_i - 1)$，然后枚举这个数的倍数，令 $ans = ans + T_i imes T_{ki}$。

就做完啦~~

令 $M$ 为其中最大的数字，

时间复杂度为 $O(n + M log M)$，空间复杂度为 $O(M)$。

 1 #include <cstdio>
 2 typedef long long LL;
 3 #define N 2000000 + 5
 4 
 5 int n, Max, T[N];
 6 LL ans;
 7 
 8 inline int getint()
 9 {
10     char ch = '
';
11     for (; ch > '9' || ch < '0'; ch = getchar()) ;
12     int res = ch - '0';
13     for (ch = getchar(); ch >= '0' && ch <= '9'; ch = getchar())
14         res = (res << 3) + (res << 1) + ch - '0';
15     return res;
16 }
17 
18 int main()
19 {
20     n = getint();
21     for (int i = 1; i <= n; i ++)
22     {
23         int t = getint();
24         Max = Max > t ? Max : t;
25         T[t] ++;
26     }
27     for (int i = 1; i <= Max; i ++)
28         if (T[i])
29         {
30             ans += (LL) T[i] * (T[i] - 1);
31             for (int j = i << 1; j <= Max; j += i)
32                 ans += (LL) T[i] * T[j];
33         }
34     printf("%lld
", ans);
35     return 0;
36 }

4146_Gromah