BZOJ 1114 Number theory（莫比乌斯反演+预处理）

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=71738

题意：给你一个整数序列a1, a2, a3, ... , an。求gcd(ai, aj) = 1 且 i < j的对数。

思路：利用莫比乌斯反演很快就能得到公式，但是求解时我们要知道序列中1, 2, 3, ... , max(a1, a2, ... , an)的倍数各是多少。我们用num[i]=k，来表示序列中有k个数是i的倍数，那么这部分对结果的影响是mu[i]*(k - 1) * k / 2。最后的结果就是sigma(mu[i]*(k - 1) * k / 2)。

code：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 typedef long long LL;

 const int MAXN = ;

 int num[MAXN];        // num[i]表示 满足(i|ak)的个数

 int tmp[MAXN];        // 标记哪些数有

 bool check[MAXN];

 int primes[MAXN];

 int mu[MAXN];

 void moblus()

 {

     memset(check, false, sizeof(check));

     mu[] = ;

     int cnt = ;

     for (int i = ; i < MAXN; ++i) {

         if (!check[i]) {

             primes[cnt++] = i;

             mu[i] = -;

         }

         for (int j = ; j < cnt; ++j) {

             if (i * primes[j] > MAXN) break;

             check[i * primes[j]] = true;

             if (i % primes[j] == ) {

                 mu[i * primes[j]] = ;

                 break;

             } else {

                 mu[i * primes[j]] = -mu[i];

             }

         }

     }

 }

 int main()

 {

     moblus();

     int n;

     while (scanf("%d", &n) != EOF) {

         memset(num, , sizeof(num));

         memset(tmp, , sizeof(tmp));

         int tmax = ;

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

             int x;

             scanf("%d", &x);

             ++tmp[x];

             tmax = max(tmax, x);

         }

         for (int i = ; i <= tmax; ++i) {

             for (int j = i; j <= tmax; j += i) {

                 num[i] += tmp[j];

             }

         }

         LL ans = ;

         for (int i = ; i <= tmax; ++i) {

             ans += (LL)mu[i] * num[i] * (num[i] - ) / ;

         }

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

     }

     return ;

 }

巴特西

BZOJ 1114 Number theory（莫比乌斯反演+预处理）

最新文章

热门文章