BZOJ 4146 [AMPPZ2014] Divisors 解题报告

时间：2021-09-10 08:31:37

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

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

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

就做完啦~~

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

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

 #include <cstdio>

 typedef long long LL;

 #define N 2000000 + 5

 int n, Max, T[N];

 LL ans;

 inline int getint()

 {

     char ch = '\n';

     for (; ch > '' || ch < ''; ch = getchar()) ;

     int res = ch - '';

     for (ch = getchar(); ch >= '' && ch <= ''; ch = getchar())

         res = (res << ) + (res << ) + ch - '';

     return res;

 }

 int main()

 {

     n = getint();

     for (int i = ; i <= n; i ++)

     {

         int t = getint();

         Max = Max > t ? Max : t;

         T[t] ++;

     }

     for (int i = ; i <= Max; i ++)

         if (T[i])

         {

             ans += (LL) T[i] * (T[i] - );

             for (int j = i << ; j <= Max; j += i)

                 ans += (LL) T[i] * T[j];

         }

     printf("%lld\n", ans);

     return ;

 }

4146_Gromah

相关文章