mobius反演讲解

By | 01月08日
Advertisement

  mobius反演的基本形式为,假设知道函数F(x)=Σf(d) d|x,那么我们可以推出f(x)=Σmiu(d)*F(x/d) d|x,另一基本形式为假设知道函数F(x)=Σf(d) x|d,那么我们可以推出f(x)=Σmiu(d)*F(d/x) x|d,第二种形式可以由容斥定理得出,在此不再赘述。

  我们由一个例子来了解mobius反演的作用。

  求解ans=Σ(0<i<=n)Σ(0<j<=m)1(gcd(i,j)=1)即n,m范围中互质点对儿数。

  我们设 F(x)为gcd(i,j)|x的点对儿数量,f(x)为gcd(i,j)=x的点对儿数量。那么易得F(x)=Σf(d) x|d,那么由第二形式可得f(x)=Σmiu(d)*F(d/x) x|d,那么这道题就是求f(1),即f(1)=Σmiu(d)*F(d) d<=min(n,m),比较显然的是F(x)=floor(n/d)*floor(m/d)。那么我们可以得到答案的形式

  ans=Σmiu(i)*floor(n/i)*floor(m/i)。可以O(n)的求解。

  但是对于某些问题,O(n)是无法在规定时间内完成的,我们考虑w=floor(n/i)*floor(m/i),对于i递增,w为不减的,即存在连续段w值相同。那么我们可以求出mobius函数的前缀和,然后分块的来求解,我们找到w值相同的区间,即存在j,满足floor(n/j)=floor(n/i),floor(m/j)=floor(m/i),那么j=min(floor(n/floor(n/i)),floor(m/floor(m/i))),这样对于w相同的块儿一起处理就行了,这样时间复杂度就变成了O(sqrt(n))。

  基础题bzoj 2301 http://61.187.179.132/JudgeOnline/problem.php?id=2301

这道题就是多了一个容斥定理求解,基本的思路和上面的相同,可以作为练手题。

/**************************************************************
    Problem: 2301
    User: BLADEVIL
    Language: Pascal
    Result: Accepted
    Time:34964 ms
    Memory:1204 kb
****************************************************************/

//By BLADEVIL
var
    a, b, c, d, k, t                    :longint;
    ans                                 :int64;
    i                                   :longint;
    prime, miu, mindiv                  :array[0..50010] of longint;
    sum                                 :array[0..50010] of int64;

procedure make;
var
    i, j                                :longint;
begin
    miu[1]:=1;
    for i:=2 to 50000 do
    begin
        if mindiv[i]=0 then
        begin
            inc(prime[0]);
            prime[prime[0]]:=i;
            mindiv[i]:=i;
            miu[i]:=-1;
        end;
        for j:=1 to prime[0] do
        begin
            if i*prime[j]>50000 then break;
            mindiv[i*prime[j]]:=prime[j];
            if i mod prime[j]=0 then
            begin
                miu[i*prime[j]]:=0;
                break;
            end else
                miu[i*prime[j]]:=-miu[i];
        end;
    end;
    for i:=1 to 50000 do sum[i]:=sum[i-1]+miu[i];
end;

function calc(n,m:longint):longint;
var
    t, t1, t2                           :int64;
    i                                   :longint;
    xx                                  :int64;
begin
    calc:=0;
    i:=1;
    if n>m then xx:=m else xx:=n;
    while i<=xx do
    begin
        t1:=n div (n div i);
        t2:=m div (m div i);
        if t1<t2 then t:=t1 else t:=t2;
        calc:=calc+(sum[t]-sum[i-1])*(n div i)*(m div i);
        i:=t+1;
    end;
end;

begin
    make;
    readln(t);
    for i:=1 to t do
    begin
        readln(a,b,c,d,k);
        ans:=int64(calc(b div k,d div k))
            -int64(calc((c-1) div k,b div k))
            -int64(calc((a-1) div k,d div k))
            +int64(calc((a-1) div k,(c-1) div k));
        writeln(ans);
    end;
end.

Similar Posts:

  • Bzoj-2820 YY的GCD Mobius反演,分块

    题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2820 题意:多次询问,求1<=x<=N, 1<=y<=M且gcd(x,y)为质数有多少对. 首先, 由于这里是多次询问,并且数据很大,显然不能直接求解,需要做如下处理.. 整数的除法是满足结合律的,然后我们设T=p*d,有: 注意到后面部分是可以预处理出来的,那么整个ans就可以用分块处理来求了,设 那么有,考虑当p|x时,根据莫比菲斯mu(x)的性质,px除以其它非p的质

  • 2301: [HAOI2011]Problem b (Mobius反演)

    #include<bits/stdc++.h> using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const int maxn

  • SPOJ 7001. Visible Lattice Points 【mobius反演】

    #pragma comment(linker, "/STACK:102400000,102400000") #include<iostream> #include<vector> #include<algorithm> #include<cstdio> #include<queue> #include<stack> #include<string> #include<map> #includ

  • ACM 要学

    初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,p

  • [借鉴]ACM训练计划

    本文内容全为转载 看完人家的博客,发现任重道远... 一位高手对我的建议: 一般要做到50行以内的程序不用调试.100行以内的二分钟内调试成功.acm主要是考算法的 ,主要时间是花在思考算法上,不是花在写程序与debug上. 下面给个计划你练练: 第一阶段: 练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Floyd.Dijstra,BellmanFord) 2.最小生

  • 题单一:经典题

    初级: 一.基本算法: (1)枚举.(poj1753,poj2965) (2)贪心.(poj1328,poj2109,poj2586) // poj2109 为啥贪心 (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (p

  • poj 题目分类(3)

    OJ上的一些水题(可用来练手和增加自信) (poj3299,poj2159,poj2739,poj1083,poj2262,poj1503,poj3006,poj2255,poj3094) 初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图

  • POJ题目分类【实在是不知道哪个是原创了】

    初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,p

  • 学习算法之路

    第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Floyd.Dijstra,BellmanFord) 2.最小生成树(先写个prim,kruscal要用并查集,不好写) 3.大数(高精度)加减乘除 4.二分查找. (代码可在五行以内) 5.叉乘.判线段相交.然后写个凸包. 6.BFS.DFS,同时熟练hash表(要熟,要灵活,代码要简) 7.数学上的有:辗转相

  • poj 题型

    初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短路径算法(dijkstra,bellman-ford,floyd,heap+dijkstra) (poj1860,poj3259,p

Tags: