Acdream 1114 Number theory 莫比乌斯反演

http://acdream.info/problem?pid=1114

题目大意,给你一个序列a,求出这个序列中互质数的有多少对。其中所有的整数的都小于等于222222。

f(d) 为 gcd 恰好为 d 的数的对数, F(d) 为 gcd 为 d 的倍数的对数, μ(d) 表示莫比乌斯函数

F(d) = ∑ f(n) 其中( n % d == 0 )

莫比乌斯反演一下就可以得到, f(d) = ∑ μ(n / d) * F(n) 其中( n % d == 0)

所以我们最后所要的答案就是 f(1), 也就是 ∑ μ(n) * F(n)

下面代码中,cnt[d]是a这个序列中为d的倍数的数字的个数,num[d]是a这个序列中d的个数,所以F[n] = C(cnt[n], 2).

#include<cstring>
#include<iostream>
using namespace std;
typedef long long LL;
const int INF = 0x7fffffff;
const int MAXN = 222222 + 5;

LL ans;
int n, mx, a[MAXN];
int pCnt, vis[MAXN], prime[MAXN];
int mu[MAXN], cnt[MAXN], num[MAXN];
#define max(a, b) (a) > (b) ? (a) : (b)

void mobius(int n)
{
    pCnt = -1, vis[1] = mu[1] = 1;

    for(int i = 2; i <= n; ++ i)
    {
        if(!vis[i])
        {
            prime[++ pCnt] = i;
            mu[i] = -1;
        }

        for(int j = 0; j <= pCnt && i * prime[j] <= n; ++ j)
        {
            vis[i * prime[j]] = 1;

            if(i % prime[j])
                mu[i * prime[j]] = ~mu[i] + 1;
            else
                mu[i * prime[j]] = 0;
        }
    }
}

int main()
{
    mobius(222222);
    cin.sync_with_stdio(false);

    while(cin >> n)
    {
        ans = 0, mx = -INF;
        memset(cnt, 0, sizeof(cnt));
        memset(num, 0, sizeof(num));

        for(int i = 1; i <= n; ++ i)
        {
            cin >> a[i];
            mx = max(mx, a[i]);
        }

        for(int i = 1; i <= n; ++ i)
            ++ num[a[i]];

        for(int i = 1; i <= mx; ++ i)
            for(int j = i; j <= mx; j += i)
                cnt[i] += num[j];

        for(int i = 1; i <= mx; ++ i)
            ans += (mu[i] * (LL)cnt[i] * (cnt[i] - 1)) >> 1;

        cout << ans << endl;
    }

    return 0;
}

Acdream 1114 Number theory 莫比乌斯反演,布布扣,bubuko.com

时间: 08-13

Acdream 1114 Number theory 莫比乌斯反演的相关文章

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的倍数,那么这部分对结果的影响是m

ACdream 1114(莫比乌斯反演)

传送门:Number theory 题意:给n个数,n 和 每个数的范围都是 1---222222,求n个数中互质的对数. 分析:处理出每个数倍数的个数cnt[i],然后进行莫比乌斯反演,只不过这里的F(i)=cnt[i]*(cnt[i]-1)/2. #pragma comment(linker,"/STACK:1024000000,1024000000") #include <cstdio> #include <cstring> #include <st

ACdream 1148(莫比乌斯反演+分块)

传送门:GCD SUM 题意:给出N,M执行如下程序:long long  ans = 0,ansx = 0,ansy = 0;for(int i = 1; i <= N; i ++)   for(int j = 1; j <= M; j ++)       if(gcd(i,j) == 1) ans ++,ansx += i,ansy += j;cout << ans << " " << ansx << " &qu

专题练习---(数论)莫比乌斯反演

GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7026    Accepted Submission(s): 2584 Problem Description Given 5 integers: a, b, c, d, k, you're to find x in a...b, y in c...d that GCD(x, y)

hdu-1695 GCD(莫比乌斯反演)

题目链接: GCD Time Limit: 6000/3000 MS (Java/Others)     Memory Limit: 32768/32768 K (Java/Others) Problem Description Given 5 integers: a, b, c, d, k, you're to find x in a...b, y in c...d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor

hdu 1695 容斥原理或莫比乌斯反演

GCD Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 5310    Accepted Submission(s): 1907 Problem Description Given 5 integers: a, b, c, d, k, you're to find x in a...b, y in c...d that GCD(x, y)

bzoj 2820 / SPOJ PGCD 莫比乌斯反演

那啥bzoj2818也是一样的,突然想起来好像拿来当周赛的练习题过,用欧拉函数写掉的. 求$(i,j)=prime$对数 \begin{eqnarray*}\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=p]&=&\sum_{p=2}^{min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}[i⊥j]\newline&=&\sum_{p=

hdu1695(莫比乌斯反演)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1695 题意: 对于 a, b, c, d, k . 有 x 属于 [a, b],  y 属于 [c, d], 求 gcd(x, y) = k 的 x, y 的对数 . 其中 a = b = 1 . 注意: (x, y), (y, x) 算一种情况 . 思路: 莫比乌斯反演 可以参考一下: http://blog.csdn.net/lixuepeng_001/article/details/5057

算法学习——莫比乌斯反演(1)

.. 省选GG了,我果然还是太菜了.. 突然想讲莫比乌斯反演了 那就讲吧! 首先我们看一个等式-- (d|n表示d是n的约束) 然后呢,转换一下 于是,我们就发现! 没错!F的系数是有规律的! 规律is here! 公式: 这个有什么卵用呢? 假如说有一道题 F(n)可以很simple的求出来而求f(n)就比较difficult了,该怎么办呢? 然后就可以用上面的式子了 是莫比乌斯函数,十分有趣 定义如下: 若d=1,则=1 若d=p1*p2*p3...*pk,且pi为互异素数,则=(-1)^k