精华内容
下载资源
问答
  • 圆的反演性质

    2017-08-21 16:56:00
    反演的定义: 已知一圆C,圆心为O,半径为r,如果P与P’在过圆心O的直线上,且,则称P与P'关于O互为反演。 一、任意一条不过反演中心的直线,它的反形(反演后的图形)是经过反演中心的圆,反之亦然,特别地,过...

    反演的定义:

    已知一圆C,圆心为O,半径为r,如果P与P’在过圆心O的直线上,且,则称P与P'关于O互为反演。

     

    一、任意一条不过反演中心的直线,它的反形(反演后的图形)是经过反演中心的圆,反之亦然,特别地,过反演中心相交的圆,变为不过反

    演中心的相交直线。

     

    二、不过反演中心的圆,它的反形是一个圆,反演中心是这两个互为反形的圆的一个位似中心,任意一对反演点是逆对应

    点。用图形来解释,如下图:

    已知:圆C1,求圆C2

    我们设圆C1的半径为,反演半径为

    那么根据反演的定义有:

    那么,消去得到:

    反形圆的半径r2:  

     

    转载于:https://www.cnblogs.com/stepping/p/7405384.html

    展开全文
  • 为了获得有效的光谱反演指标,采用数学建模方法对横山县采集的84个土样350nm~2500nm波段的光谱曲线进行了有机质、土壤水含量和全铁土壤性质指标光谱进行反演分析。对土壤光谱进行了14种变换,经分析土壤光谱对数的...
  • 分析研究了相干光与具有空间反演对称非线性介质作用的压缩性质。对于一种非线性介质,其势能具有空间反演对称性,在此情况下介质的偶次极化率为零,对介质极化起主导作用的是它的三次极化率。因此,单模光场与此介质相互...
  • 性质1: ∑d∣n\sum_{d|n}∑d∣n​μ(d)={1,if (n = 1)0,if (n > 1)\mu{(d)}= \begin{cases} 1, & \text{if (n = 1)}\\ 0, & \text{if (n > 1)} \end{cases}μ(d)={1,...

    莫比乌斯函数的定义:𝜇(n)

    性质1:

    ∑ d ∣ n \sum_{d|n} dn μ ( d ) = { 1 , if (n = 1) 0 , if (n > 1) \mu{(d)}= \begin{cases} 1, & \text{if (n = 1)}\\ 0, & \text{if (n > 1)} \end{cases} μ(d)={1,0,if (n = 1)if (n > 1)

    性质2:

    ∑ d ∣ n \sum_{d|n} dn μ ( d ) d = φ ( n ) n \frac{\mu{(d)}}{d} =\frac{\varphi{(n)}}{n} dμ(d)=nφ(n)

    性质3:

    μ ( a ∗ b ) = μ ( a ) ∗ μ ( b ) \mu(a*b)=\mu(a)*\mu(b) μ(ab)=μ(a)μ(b)

    反演公式1:

    F ( n ) = ∑ d ∣ n f ( d ) = > f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) F(n)=\sum_{d|n}f(d) =>f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d}) F(n)=dnf(d)=>f(n)=dnμ(d)F(dn)

    反演公式2:

    F ( n ) = ∑ n ∣ d f ( d ) = > f ( n ) = ∑ n ∣ d μ ( d n ) F ( d ) F(n)=\sum_{n|d}f(d) =>f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d) F(n)=ndf(d)=>f(n)=ndμ(nd)F(d)

    展开全文
  • 提出了基于中分辨率成像光谱仪(MODIS)数据反演近海污染大气气溶胶光学性质的算法。根据近海污染大气气溶胶的成分特征构建了新的气溶胶模式;同时避开了MODIS反演算法中计算大气顶光谱反射率理论的缺陷;利用近红外...
  • 圆的反演变换

    万次阅读 2013-11-27 14:52:47
    首先,得知道什么是反演变换以及它有什么性质反演的定义: 已知一圆C,圆心为O,半径为r,如果P与P’在过圆心O的直线上,且 ,则称P与P'关于O互为反演反演性质: (1)...

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=4773


    题意:给定两个圆,告诉半径和圆心,它们是相离的,在这两个圆外给定一个点p,求符合条件:过点p的圆且与已知的两个

    外切的所有圆的总数和它们的圆心坐标和半径。



    分析:根据题意,我们设已知两个圆的半径分别为,它们的圆心分别为,设点p的坐标为


    并设要求的圆的圆心为,半径为,那么根据它们的关系我们可以很快就列出方程组:




    然后,现在的问题就是来解,但是你会发现这个方程是很难解的,因此为了简化问题,我们利用反演变换来做。



    那么,怎么用反演变换来做? 首先,得知道什么是反演变换以及它有什么性质。


    反演的定义:


    已知一圆C,圆心为O,半径为r,如果P与P’在过圆心O的直线上,且,则称P与P'关于O互为反演。


    反演的性质:


    (1)除反演中心外,平面上的每一个点都只有唯一的反演点,且这种关系是对称的,位于反演圆上的点,保持在原处,位于

    反演圆外部的点,变为圆内部的点,位于反演圆内部的点,变为圆外部的点。 举个最简单的例子,区间以1为反演

    半径,那么反演后的区间就是,这就是一维反演,而圆的反演是二维反演。


    (2)任意一条不过反演中心的直线,它的反形是经过反演中心的圆,反之亦然,特别地,过反演中心相交的圆,变为不过反

    演中心的相交直线。





    定理:不过反演中心的圆,它的反形是一个圆,反演中心是这两个互为反形的圆的一个位似中心,任意一对反演点是逆对应

    点。用图形来解释,如下图:




    那么,对于一个不过反演中心的圆,怎样求它的反形圆?


    很容易知道我们只需要求出反形圆的圆心和半径就可以了。


    对于上图我们设圆C1的半径为,C2的半径为,反演半径为


    那么根据反演的定义有:




    那么,消去得到:




    这样我们就得到了反形圆的半径,那么还要求反形圆的圆心。



    由于C1和O两点的坐标已知,而且我们知道O,C1,C2位于同一直线上,那么很明显对于C2的坐标,我们可以这样计算:


    设O的坐标为,C1的坐标为,C2的坐标为


    那么有:




    至于由上面解处可以很容易得到,这样我们就完成了圆的反演变换。



    由于本题的做法是这样的,先以点P为为反演中心,反演半径随便设置都可以,为了计算方便就设为1,把圆C1和圆C2反演后再求这两个圆的

    公切线,再把这个公切线反演回去,那么就是一个过点P的圆,且与原来的C1和C2相切。



    那么接下来就是如何计算两个圆的公切线了。这里只需要考虑公切线在同一侧的情况。那么,这个自己画图就能很容易计算了。

    找到公切线后还要把它反演成圆,这个圆还经过P点,那么很容易得到了。


    #include <iostream>
    #include <string.h>
    #include <stdio.h>
    #include <math.h>
    
    using namespace std;
    double const eps = 1e-8;
    
    struct Point
    {
        double x,y;
        Point(double a = 1.0,double b = 1.0):x(a),y(b){}
        Point operator + (const Point &a)
        {
            return Point(x+a.x,y+a.y);
        }
        Point operator - (const Point &a)
        {
            return Point(x-a.x,y-a.y);
        }
        Point operator * (const double a)
        {
            return Point(a*x,a*y);
        }
        Point Trans()
        {
            return Point(-y,x);
        }
        void Input()
        {
            scanf("%lf%lf",&x,&y);
        }
    } ;
    
    struct Circle
    {
        Point o;
        double r;
        Circle(Point a = Point(),double b = 1.0):o(a),r(b) {}
        Point getPoint(double alpha)
        {
            return o + Point(r*cos(alpha),r*sin(alpha));
        }
        void Input()
        {
            o.Input();
            scanf("%lf",&r);
        }
        void Output()
        {
            printf("%.8lf %.8lf %.8lf\n",o.x,o.y,r);
        }
    } ;
    
    Point p;
    Circle c[15];
    
    double dist(Point A,Point B)
    {
        return sqrt((A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y));
    }
    
    double cross(Point A,Point B,Point C)
    {
        return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x);
    }
    
    int sign(double x)
    {
        return (x > eps) - (x < -eps);
    }
    
    Circle Inverse(Circle C)
    {
        Circle T;
        double t = dist(C.o,p);
        double x = 1.0 / (t - C.r);
        double y = 1.0 / (t + C.r);
        T.r = (x - y) / 2.0;
        double s = (x + y) / 2.0;
        T.o = p + (C.o - p) * (s / t);
        return T;
    }
    
    void add(Point a,Point b,int &k)
    {
        double t = cross(a,p,b);
        if(t < 0) t = -t;
        double d = dist(a,b);
        t /= d;
        if(t > eps)
        {
            double w = 0.5 / t;
            Point dir = (b-a).Trans();
            Point a1 = p + dir * (w / d);
            Point b1 = p - dir * (w / d);
            if(fabs(cross(a,b,a1)) < fabs(cross(a,b,b1)))
               c[k++] = Circle(a1,w);
            else
               c[k++] = Circle(b1,w);
        }
    }
    
    int Work()
    {
        c[0] = Inverse(c[0]);
        c[1] = Inverse(c[1]);
        if(c[1].r > c[0].r) swap(c[1],c[0]);
        Point v = c[1].o - c[0].o;
        double alpha = atan2(v.y,v.x);
        double d = dist(c[0].o,c[1].o);
        double beta  = acos((c[0].r - c[1].r) / d);
        int k = 2;
        Point a = c[0].getPoint(alpha + beta);
        Point b = c[1].getPoint(alpha + beta);
        if(sign(cross(a,c[0].o,b)) == sign(cross(a,p,b)) &&
           sign(cross(a,c[1].o,b)) == sign(cross(a,p,b)))
            add(a,b,k);
        a = c[0].getPoint(alpha - beta);
        b = c[1].getPoint(alpha - beta);
        if(sign(cross(a,c[0].o,b)) == sign(cross(a,p,b)) &&
           sign(cross(a,c[1].o,b)) == sign(cross(a,p,b)))
            add(a,b,k);
        return k - 2;
    }
    
    int main()
    {
        int T;
        scanf("%d",&T);
        while(T--)
        {
            c[0].Input();
            c[1].Input();
            p.Input();
            int num = Work();
            printf("%d\n",num);
            for(int i=0;i<num;i++)
                c[i+2].Output();
        }
        return 0;
    }
    



    展开全文
  • 炫酷反演魔术

    2018-08-10 17:04:56
    炫酷反演魔术 VFleaKing ICPC WC 2014 Day 7 小学生的容斥 中学生的容斥 容斥的幕后 另一个角度 一点小性质 魔术
  • 反演结果表明,其各通道对海冰性质有很好的反映,资料信号比较稳定,对不同密集度和厚度的冰有较好的区分,相对NOAA/AvHRR和HY-1A资料有更好的实际应用价值;Terra/MODIs和HY-1A/COCTS海冰遥感反演结果对比也为HY-1A...
  • 文章目录 莫比乌斯反演 引入 公式 性质 模板 公式证明 莫比乌斯函数前缀和 题目练习 完全平方数 [HAOI2011]Problemb YY的GCD [SDOI2014]数表 [国家集训队]Crash的数字表格/JZPTAB [SDOI2015]约数个数和 寒假疫情期间...

    寒假疫情期间跟着lmm学了一遍,完全是懵逼到底状态,以至于后面考到或者做到相关知识的题目,完全是非洲人。今天跟着h老师重新学了一遍,虽然可能自己还是不会推🍔,但至少看得懂了吧

    莫比乌斯反演


    引入

    F ( n ) = ∑ d ∣ n f ( d ) F(n)=\sum_{d|n}f(d) F(n)=dnf(d)
    通过这个例子,可以暴力打出下列表

    F ( 1 ) F(1) F(1) f ( 1 ) f(1) f(1)
    F ( 2 ) F(2) F(2) f ( 1 ) + f ( 2 ) f(1)+f(2) f(1)+f(2)
    F ( 3 ) F(3) F(3) f ( 1 ) + f ( 3 ) f(1)+f(3) f(1)+f(3)
    F ( 4 ) F(4) F(4) f ( 1 ) + f ( 2 ) + f ( 4 ) f(1)+f(2)+f(4) f(1)+f(2)+f(4)
    F ( 5 ) F(5) F(5) f ( 1 ) + f ( 5 ) f(1)+f(5) f(1)+f(5)
    F ( 6 ) F(6) F(6) f ( 1 ) + f ( 2 ) + f ( 3 ) + f ( 6 ) f(1)+f(2)+f(3)+f(6) f(1)+f(2)+f(3)+f(6)
    F ( 7 ) F(7) F(7) f ( 1 ) + f ( 7 ) f(1)+f(7) f(1)+f(7)
    F ( 8 ) F(8) F(8) f ( 1 ) + f ( 2 ) + f ( 4 ) + f ( 8 ) f(1)+f(2)+f(4)+f(8) f(1)+f(2)+f(4)+f(8)

    转换一下,得到新表

    f ( 1 ) f(1) f(1) F ( 1 ) F(1) F(1)
    f ( 2 ) f(2) f(2) F ( 2 ) − F ( 1 ) F(2)-F(1) F(2)F(1)
    f ( 3 ) f(3) f(3) F ( 3 ) − F ( 1 ) F(3)-F(1) F(3)F(1)
    f ( 4 ) f(4) f(4) F ( 4 ) − F ( 2 ) F(4)-F(2) F(4)F(2)
    f ( 5 ) f(5) f(5) F ( 5 ) − F ( 1 ) F(5)-F(1) F(5)F(1)
    f ( 6 ) f(6) f(6) F ( 6 ) − F ( 3 ) − F ( 2 ) + F ( 1 ) F(6)-F(3)-F(2)+F(1) F(6)F(3)F(2)+F(1)
    f ( 7 ) f(7) f(7) F ( 7 ) − F ( 1 ) F(7)-F(1) F(7)F(1)
    f ( 8 ) f(8) f(8) F ( 8 ) − F ( 4 ) F(8)-F(4) F(8)F(4)

    看看能观察到 f f f F F F之间存在什么规律??
    🚨 重点关注 f ( 1 ) , f ( 4 ) , f ( 6 ) , f ( 8 ) f(1),f(4),f(6),f(8) f(1),f(4),f(6),f(8)
    🧀 f ( 6 ) = F ( 6 1 ) − F ( 6 2 ) − F ( 6 3 ) + F ( 6 6 ) f(6)=F(\frac{6}{1})-F(\frac{6}{2})-F(\frac{6}{3})+F(\frac{6}{6}) f(6)=F(16)F(26)F(36)+F(66)
    在这里插入图片描述

    发现规律 其实是知道公式了

    F ( n d ) F(\frac{n}{d}) F(dn) d d d质因数分解 p 1 k 1 . . . p i k i p_1^{k_1}...p_i^{k_i} p1k1...piki,如果各质数指数均为 1 1 1,则该 F ( n d ) F(\frac{n}{d}) F(dn)才会存在 ,特别地,当 d = 1 d=1 d=1时也一定存在

    🍗: f ( 8 ) = F ( 8 1 ) − F ( 8 2 ) f(8)=F(\frac{8}{1})-F(\frac{8}{2}) f(8)=F(18)F(28)
    F ( 8 1 ) : 1 F(\frac{8}{1}):1 F(18)1存在
    F ( 8 2 ) : 2 F(\frac{8}{2}):2 F(28)2质因数分解 2 1 2^1 21,存在
    F ( 2 ) = F ( 8 4 ) : 4 F(2)=F(\frac{8}{4}):4 F(2)=F(48)4质因数分解 2 2 2^2 22,不存在
    F ( 1 ) = F ( 8 8 ) : 8 F(1)=F(\frac{8}{8}):8 F(1)=F(88)8质因数分解 2 3 2^3 23,不存在

    F ( n d ) F(\frac{n}{d}) F(dn)前面的符号取决于 d d d所含质因子的个数/种类的奇偶性, ( − 1 ) k (-1)^k (1)k

    🍗: f ( 6 ) = F ( 6 1 ) − F ( 6 2 ) − F ( 6 3 ) + F ( 6 6 ) f(6)=F(\frac{6}{1})-F(\frac{6}{2})-F(\frac{6}{3})+F(\frac{6}{6}) f(6)=F(16)F(26)F(36)+F(66)
    F ( 6 1 ) : 1 F(\frac{6}{1}):1 F(16)1不含任何质因子,系数为 ( − 1 ) 0 = 1 (-1)^0=1 (1)0=1
    F ( 6 2 ) : 2 F(\frac{6}{2}):2 F(26)2含质因子 2 2 2,系数为 ( − 1 ) 1 = − 1 (-1)^1=-1 (1)1=1
    F ( 6 3 ) : 3 F(\frac{6}{3}):3 F(36)3含质因子 3 3 3,系数为 ( − 1 ) 1 = − 1 (-1)^1=-1 (1)1=1
    F ( 6 6 ) : 6 F(\frac{6}{6}):6 F(66)6含质因子 2 , 3 2,3 2,3,系数为 ( − 1 ) 2 = 1 (-1)^2=1 (1)2=1
    在这里插入图片描述


    公式

    引入中发现的规律经过数学 提炼加工打磨 规范,将 ( − 1 ) k (-1)^k (1)k定义为 μ ( i ) \mu (i) μ(i)
    便成为了一个优美的🍔
    F ( n ) = ∑ d ∣ n f ( n ) ⇒ f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) F(n)=\sum_{d|n}f(n)\Rightarrow f(n)=\sum_{d|n}\mu (d)F(\frac{n}{d}) F(n)=dnf(n)f(n)=dnμ(d)F(dn)

    其中 μ ( d ) \mu(d) μ(d)为莫比乌斯函数,定义如下:

    1. d = 1 , μ ( d ) = 1 d=1,\mu(d)=1 d=1,μ(d)=1
    2. d d d能改写为 p 1 p 2 . . . p k p_1p_2...p_k p1p2...pk互异质数的积,则 μ ( d ) = ( − 1 ) k \mu(d)=(-1)^k μ(d)=(1)k
    3. o t h e r w i s e otherwise otherwise,其余情况 μ ( d ) = 0 \mu(d)=0 μ(d)=0

    性质

    • 性质一:
      对于任意的正整数 n n n有:
      ∑ d ∣ n μ ( d ) = { 1 ( n = 1 ) 0 ( n ≠ 1 ) \sum_{d|n}\mu(d)=\left\{ \begin{aligned} 1&&(n=1)\\ 0&&(n≠1) \end{aligned} \right. dnμ(d)={10(n=1)(n=1)
      证明:
      Ⅰ. 当 n = 1 n=1 n=1时, μ ( 1 ) = 1 \mu(1)=1 μ(1)=1,显然成立
      Ⅱ. 当 n ≠ 1 n≠1 n=1时,将 n n n质因数分解为 p 1 a 1 p 2 a 2 . . . p k a i p_1^{a_1}p_2^{a_2}...p_k^{a_i} p1a1p2a2...pkai
      只有所有质因子的指数都为 1 1 1的因数的 μ \mu μ值不为 0 0 0
      则其中有 x x x个不同质因子的个数为 C k x C_k^x Ckx,于是有
      ∑ d ∣ n μ ( d ) = C k 0 − C k 1 + C k 2 . . . . = ∑ i = 0 k ( − 1 ) i C k i \sum_{d|n}\mu(d)=C_k^0-C_k^1+C_k^2....=\sum_{i=0}^k(-1)^iC_k^i dnμ(d)=Ck0Ck1+Ck2....=i=0k(1)iCki
      🧀二项式展开公式为:
      ( X + Y ) n = ∑ i = 0 n C n i X i Y n − i (X+Y)^n=\sum_{i=0}^nC_n^iX^iY^{n-i} (X+Y)n=i=0nCniXiYni
      X = 1 , Y = − 1 X=1,Y=-1 X=1,Y=1带入即可得到:
      ∑ i = 0 k ( − 1 ) i C k i = [ 1 + ( − 1 ) ] k = 0 \sum_{i=0}^k(-1)^iC_k^i=[1+(-1)]^k=0 i=0k(1)iCki=[1+(1)]k=0

    • 性质二:
      对于任意的正整数 n n n有:
      ∑ d ∣ n μ ( d ) d = ϕ ( n ) n \sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n} dndμ(d)=nϕ(n)
      证明:
      ∑ d ∣ n μ ( d ) d = ϕ ( n ) n ⇔ n × ∑ d ∣ n μ ( d ) d = ϕ ( n ) \sum_{d|n}\frac{\mu(d)}{d}=\frac{\phi(n)}{n}\Leftrightarrow n\times \sum_{d|n}\frac{\mu(d)}{d}=\phi(n) dndμ(d)=nϕ(n)n×dndμ(d)=ϕ(n)
      F ( n ) = n , f ( n ) = ϕ ( n ) F(n)=n,f(n)=\phi(n) F(n)=n,f(n)=ϕ(n),则有
      f ( n ) = n × ∑ d ∣ n μ ( d ) d = ∑ d ∣ n μ ( d ) n d = ∑ d ∣ n μ ( d ) F ( n d ) f(n)=n\times \sum_{d|n}\frac{\mu(d)}{d}=\sum_{d|n}\mu(d)\frac{n}{d}=\sum_{d|n}\mu(d)F(\frac{n}{d}) f(n)=n×dndμ(d)=dnμ(d)dn=dnμ(d)F(dn)
      🚨不要忘记 f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) f(n)=\sum_{d|n}\mu(d)F(\frac{n}{d}) f(n)=dnμ(d)F(dn)成立的前提是 F ( n ) = ∑ d ∣ n f ( d ) F(n)=\sum_{d|n}f(d) F(n)=dnf(d)
      所以如果性质二要想成立,就必须再证明 n = ∑ d ∣ n ϕ ( d ) n=\sum_{d|n}\phi(d) n=dnϕ(d)
      考虑从物理意义角度出发
      k ∈ [ 1 , n ] , g c d ( n , k ) = d ⇒ g c d ( n / d , k ) = 1 k∈[1,n],gcd(n,k)=d\Rightarrow gcd(n/d,k)=1 k[1,n]gcd(n,k)=dgcd(n/d,k)=1,将 k k k分到 C n / d C_{n/d} Cn/d类中
      🍗: n = 8 n=8 n=8
      { 1 , 3 , 5 , 7 g c d = 1 ϕ ( 8 1 ) = 4 2 , 6 g c d = 2 ϕ ( 8 2 ) = 2 4 g c d = 4 ϕ ( 8 4 ) = 1 8 g c d = 8 ϕ ( 8 8 ) = 1 \left\{ \begin{aligned} 1,3,5,7&&gcd=1&&\phi(\frac{8}{1})=4\\ 2,6&&gcd=2&&\phi(\frac{8}{2})=2\\ 4&&gcd=4&&\phi(\frac{8}{4})=1\\ 8&&gcd=8&&\phi(\frac{8}{8})=1 \end{aligned} \right. 1,3,5,72,648gcd=1gcd=2gcd=4gcd=8ϕ(18)=4ϕ(28)=2ϕ(48)=1ϕ(88)=1
      在这里插入图片描述

    • 性质三:
      莫比乌斯函数是一个积性函数
      但我不会证明
      在这里插入图片描述

    🧀
    积性函数的定义:对于任意互质的整数 a a a b b b有性质 f ( a b ) = f ( a ) f ( b ) f(ab)=f(a)f(b) f(ab)=f(a)f(b)的数论函数
    完全积性函数定义:对于任意的整数 a a a b b b f ( a b ) = f ( a ) f ( b ) f(ab)=f(a)f(b) f(ab)=f(a)f(b)的数论函数
    积性函数的性质:

    1. f ( 1 ) = 1 f(1)=1 f(1)=1
    2. 积性函数的前缀和也是积性函数

    模板

    因为莫比乌斯函数是一个积性函数,我们就可以线性筛求出其值
    由此联想到我们以前会的求质数的欧拉筛法

    void sieve() {
    	mu[1] = 1;
    	for( int i = 2;i <= n;i ++ ) {
    		if( ! vis[i] ) {
    			vis[i] = 1;
    			mu[i] = -1;
    			prime[++ cnt] = i;
    		}
    		for( int j = 1;j <= cnt && i * prime[j] <= n;j ++ ) {
    			vis[i * prime[j]] = 1;
    			if( i % prime[j] == 0 ) {
    				mu[i * prime[j]] = 0; //i*prime[j]这个数至少含有prime[j]^2 
    				break;
    			}
    			mu[i * prime[j]] = - mu[i];//多了prime[j]这一种新的质因子 所以要与原来取相反数
    			/*
    			只要i*prime[j]含有pi^2
    			早晚都会进if语句
    			*/ 
    		}
    	}
    }
    

    公式证明

    说到底,好像我们似乎貌似仿佛并没有证明这个定理,就直接提上裤子跑了


    • 形式一
      证明:
      F ( n ) = ∑ d ∣ n f ( n ) ⇒ f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) = ∑ d ∣ n μ ( d ) ∑ k ∣ n d f ( k ) F(n)=\sum_{d|n}f(n)\Rightarrow f(n)=\sum_{d|n}\mu (d)F(\frac{n}{d})=\sum_{d|n}\mu(d)\sum_{k|\frac{n}{d}}f(k) F(n)=dnf(n)f(n)=dnμ(d)F(dn)=dnμ(d)kdnf(k)
      d ∣ n , k ∣ n d ⇒ k ∣ n {d|n,k|\frac{n}{d}\Rightarrow k|n} dn,kdnkn,可以感性理解 d d d取不同值, k k k会把 n n n所有因数都枚举到
      于是可以把 k k k固定下来,更改 d d d的取值范围,类似于两层循环顺序的互调??
      在这里插入图片描述

    = ∑ k ∣ n f ( k ) ∑ d ∣ n k μ ( d ) =\sum_{k|n}f(k)\sum_{d|\frac{n}{k}}\mu(d) =knf(k)dknμ(d)
    将性质一的结论运用上, ∑ d ∣ n k μ ( d ) \sum_{d|\frac{n}{k}}\mu(d) dknμ(d)当且仅当 n k = 1 \frac{n}{k}=1 kn=1时,求和莫比乌斯函数值 ≠ 0 ≠0 =0
    = f ( n ) =f(n) =f(n)
    证明过程用到了性质一,性质一本身其实是独立于公式的,所以并不是伪证


    • 形式二
      F ( n ) = ∑ n ∣ d f ( d ) ⇒ f ( n ) = ∑ n ∣ d μ ( d n ) F ( d ) F(n)=\sum_{n|d}f(d)\Rightarrow f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d) F(n)=ndf(d)f(n)=ndμ(nd)F(d)
      证明:
      与形式一的证明大致相同
      k = d n k=\frac{d}{n} k=nd
      = ∑ k = 1 + ∞ μ ( k ) F ( n × k ) = ∑ k = 1 + ∞ μ ( k ) ∑ n × k ∣ p f ( p ) = ∑ n ∣ p f ( p ) ∑ k ∣ p n μ ( k ) =\sum_{k=1}^{+∞}\mu(k)F(n\times k)=\sum_{k=1}^{+∞}\mu(k)\sum_{n\times k|p}f(p)=\sum_{n|p}f(p)\sum_{k|\frac{p}{n}}\mu(k) =k=1+μ(k)F(n×k)=k=1+μ(k)n×kpf(p)=npf(p)knpμ(k)
      在这里插入图片描述

    当且仅当 p n = 1 , p = n \frac{p}{n}=1,p=n np=1,p=n ∑ k ∣ n p μ ( k ) = 1 \sum_{k|\frac{n}{p}}\mu(k)=1 kpnμ(k)=1,其余全为 0 0 0
    = f ( n ) =f(n) =f(n)
    一般这种形式更常用一些


    莫比乌斯函数前缀和

    基本上莫比乌斯反演的题目都会和分块绑定在一起,此时的莫比乌斯函数就需要进行前缀和
    接下来就让我们一起来深挖一下分块部分
    🍗
    Q = ∑ i ∣ d μ ( i ) ⌊ n i ⌋ Q=\sum_{i|d}\mu(i)\lfloor{\frac{n}{i}}\rfloor Q=idμ(i)in
    不妨设 n = 10 n=10 n=10,如果按照 ⌊ n i ⌋ \lfloor{\frac{n}{i}}\rfloor in 1 ≤ i ≤ n 1\le i\le n 1in进行分类
    则有 10 = { 1 } , 5 = { 2 } , 3 = { 3 } , 2 = { 4 , 5 } , 1 = { 6 , 7 , 8 , 9 , 10 } 10=\{1\},5=\{2\},3=\{3\},2=\{4,5\},1=\{6,7,8,9,10\} 10={1},5={2},3={3},2={4,5},1={6,7,8,9,10}
    反映在平面直角坐标系上,看看是什么样👀
    在这里插入图片描述
    按照 x \sqrt{x} x 做分割线,前半段的 x x x最多只有 x \sqrt{x} x 段,后半段的 y y y最多只有 x \sqrt{x} x
    在这里插入图片描述拼接在一起,则 ⌊ n i ⌋ \lfloor{\frac{n}{i}}\rfloor in最多只有 2 n 2\sqrt{n} 2n 个取值
    n / i n/i n/i即为 i i i所在的块, n / ( n / i ) n/(n/i) n/(n/i)则为该块右端点值
    在这里插入图片描述

    block = n / i;
    r = n / block;
    

    因为 [ i , n / ( n / i ) ] [i,n/(n/i)] [i,n/(n/i)]这一段的 ⌊ n i ⌋ \lfloor{\frac{n}{i}}\rfloor in均相等
    所以我们就可以对 μ \mu μ进行前缀和,直接 O ( 1 ) O(1) O(1)计算出这一段区间的 s u m sum sum
    就不必再老实地一个一个往后推
    老实人永远会被出题人吊起来抽
    这个思想会在后面的题里反复出现,所以提前放出来


    题目练习

    题解和代码后续会补上


    完全平方数

    • solution

    考虑二分答案,转化为求 [ 1 , x ] [1,x] [1,x]之间的无平方因子的个数
    t o t = 0 tot=0 tot=0个质数乘积的平方的倍数的数的个数( 1 1 1的倍数)
    − 1 -1 1个质数乘积的平方的倍数的数的个数( 4 [ 2 2 ] 4[2^2] 4[22]的倍数, 9 [ 3 2 ] 9[3^2] 9[32]的倍数…)
    + 2 +2 +2个质数乘积的平方的倍数的数的个数( 36 [ ( 2 × 3 ) 2 ] 36[(2\times 3)^2] 36[(2×3)2]的倍数…)
    发现每个乘积前面的系数刚好是 μ ( i ) \mu(i) μ(i)
    🍗: μ ( 3 ) = − 1 \mu(3)=-1 μ(3)=1,故 9 9 9对答案的贡献为负, μ ( 6 ) = 1 \mu(6)=1 μ(6)=1,故 36 36 36对答案的贡献为正
    x x x以内的 i 2 i^2 i2的个数为 x i 2 \frac{x}{i^2} i2x
    ⇒ t o t ( x ) = ∑ i = 1 x μ ( i ) x i 2 \Rightarrow tot(x)=\sum_{i=1}^{\sqrt{x}}\mu(i)\frac{x}{i^2} tot(x)=i=1x μ(i)i2x
    这道题仅是莫比乌斯函数的运用,并非莫比乌斯反演
    在这里插入图片描述

    • code
    #include <cstdio>
    #define int long long
    #define maxn 1000005
    int T, k, cnt;
    int mu[maxn], prime[maxn];
    bool vis[maxn];
    
    void init() {
    	mu[1] = 1;
    	for( int i = 2;i < maxn;i ++ ) {
    		if( ! vis[i] ) mu[i] = -1, prime[++ cnt] = i;
    		for( int j = 1;j <= cnt && i * prime[j] < maxn;j ++ ) {
    			vis[i * prime[j]] = 1;
    			if( i % prime[j] == 0 ) {
    				mu[i * prime[j]] = 0;
    				break;
    			}
    			mu[i * prime[j]] = -mu[i];
    		}
    	}	
    }
    
    int check( int x ) {
    	int ans = 0;
    	for( int i = 1;i * i <= x;i ++ )
    		ans += x / ( i * i ) * mu[i];
    	return ans;
    }
    
    signed main() {
    	init();
    	scanf( "%lld", &T );
    	while( T -- ) {
    		scanf( "%lld", &k );
    		int l = 1, r = ( k << 1 );
    		while( l <= r ) {
    			int mid = ( l + r ) >> 1;
    			if( check( mid ) >= k ) r = mid - 1;
    			else l = mid + 1;
    		}
    		if( check( l ) == k ) printf( "%lld\n", l );
    		else printf( "%lld\n", r );
    	}
    	return 0;
    }
    

    [HAOI2011]Problemb

    • solution

    a ≤ x ≤ b , c ≤ y ≤ d a\le x\le b,c\le y\le d axb,cyd二维差分成四个询问
    每次询问 1 ≤ x ≤ n , 1 ≤ y ≤ m 1\le x\le n,1\le y\le m 1xn,1ym g c d ( x , y ) = k gcd(x,y)=k gcd(x,y)=k的数对数量
    然后再转化为 1 ≤ x ≤ n k , 1 ≤ y ≤ m k 1\le x\le \frac{n}{k},1\le y\le \frac{m}{k} 1xkn,1ykm内的互质的数对数量

    定义 f ( i ) : g c d ( x , y ) = i f(i):gcd(x,y)=i f(i):gcd(x,y)=i的数对数量, F ( i ) : i ∣ g c d ( x , y ) F(i):i|gcd(x,y) F(i):igcd(x,y)的数对数数量
    ( 1 ≤ x ≤ n , 1 ≤ y ≤ m ) (1\le x\le n,1\le y\le m) (1xn,1ym)

    ⇒ F ( i ) = ⌊ n i ⌋ ⌊ m i ⌋ ⇒ f ( i ) = ∑ i ∣ d μ ( d i ) F ( i ) = ∑ i ∣ d μ ( d i ) ⌊ n i ⌋ ⌊ m i ⌋ \Rightarrow F(i)=\lfloor{\frac{n}{i}}\rfloor\lfloor{\frac{m}{i}}\rfloor\Rightarrow f(i)=\sum_{i|d}\mu(\frac{d}{i})F(i)=\sum_{i|d}\mu(\frac{d}{i})\lfloor{\frac{n}{i}}\rfloor\lfloor{\frac{m}{i}}\rfloor F(i)=inimf(i)=idμ(id)F(i)=idμ(id)inim
    🧀 ⌊ n i ⌋ ⌊ m i ⌋ \lfloor{\frac{n}{i}}\rfloor\lfloor{\frac{m}{i}}\rfloor inim其实是一段一段的区间,最多 2 ( n + m ) 2(\sqrt{n}+\sqrt{m}) 2(n +m )个,从这里入手枚举
    那么就需要对前面的 ∑ i ∣ d μ ( d i ) \sum_{i|d}\mu(\frac{d}{i}) idμ(id)前缀和

    • code
    #include <cstdio>
    #include <iostream>
    using namespace std;
    #define int long long
    #define maxn 50005
    int n, a, b, c, d, k, cnt;
    bool vis[maxn];
    int prime[maxn], mu[maxn], pre[maxn];
    
    void init() {
    	mu[1] = 1;	
    	for( int i = 2;i < maxn;i ++ ) {
    		if( ! vis[i] ) prime[++ cnt] = i, mu[i] = -1;
    		for( int j = 1;j <= cnt && i * prime[j] < maxn;j ++ ) {
    			vis[i * prime[j]] = 1;
    			if( i % prime[j] == 0 ) {
    				mu[i * prime[j]] = 0;
    				break;
    			}
    			mu[i * prime[j]] = -mu[i];
    		}
    	}
    	for( int i = 1;i < maxn;i ++ ) pre[i] = pre[i - 1] + mu[i];
    }
    
    int calc( int n, int m ) {
    	if( n > m ) swap( n, m );
    	int last, ans = 0;
    	for( int i = 1;i <= n;i = last + 1 ) {
    		last = min( n / ( n / i ), m / ( m / i ) );
    		ans += ( pre[last] - pre[i - 1] ) * ( n / i ) * ( m / i );
    	}
    	return ans;
    }
    
    signed main() {
    	init();
    	scanf( "%lld", &n );
    	for( int i = 1, a, b, c, d, k;i <= n;i ++ ) {
    		scanf( "%lld %lld %lld %lld %lld", &a, &b, &c, &d, &k );
    		a --, c --;
    		a /= k, b /= k, c /= k, d /= k;
    		printf( "%lld\n", calc( b, d ) - calc( a, d ) - calc( b, c ) + calc( a, c ) );
    	}
    	return 0;
    }
    

    YY的GCD

    • solution

    既然要求 g c d ( x , y ) gcd(x,y) gcd(x,y)为质数,而且发现这道题跟上一道problem b很像
    先枚举质数,剩下的不就是求 1 ≤ x ≤ n , 1 ≤ y ≤ m , g c d ( n , m ) = 1 1\le x\le n,1\le y\le m,gcd(n,m)=1 1xn,1ym,gcd(n,m)=1的数对数量??

    定义 f ( i ) : g c d ( x , y ) = i f(i):gcd(x,y)=i f(i):gcd(x,y)=i的数对数量, F ( i ) : i ∣ g c d ( x , y ) F(i):i|gcd(x,y) F(i):igcd(x,y)的数对数数量
    ( 1 ≤ x ≤ n , 1 ≤ y ≤ m ) (1\le x\le n,1\le y\le m) (1xn,1ym)
    F ( i ) = ⌊ n i ⌋ ⌊ m i ⌋ ⇒ f ( i ) = ∑ i ∣ d μ ( d i ) F ( d ) = ∑ i ∣ d μ ( d i ) ⌊ n d ⌋ ⌊ m d ⌋ F(i)=\lfloor{\frac{n}{i}}\rfloor\lfloor{\frac{m}{i}}\rfloor\Rightarrow f(i)=\sum_{i|d}\mu(\frac{d}{i})F(d)=\sum_{i|d}\mu(\frac{d}{i})\lfloor{\frac{n}{d}}\rfloor\lfloor{\frac{m}{d}}\rfloor F(i)=inimf(i)=idμ(id)F(d)=idμ(id)dndm🚨 g c d ( x , y ) = i gcd(x,y)=i gcd(x,y)=i的质数已经提出来枚举了
    ⇒ a n s = ∑ p m i n ( n , m ) f ( 1 ) = ∑ p m i n ( n , m ) ∑ d = 1 m i n ( n , m ) μ ( d ) ⌊ n d × p ⌋ ⌊ m d × p ⌋ \Rightarrow ans=\sum_{p}^{min(n,m)}f(1)=\sum_{p}^{min(n,m)}\sum_{d=1}^{min(n,m)}\mu(d)\lfloor{\frac{n}{d\times p}}\rfloor\lfloor{\frac{m}{d\times p}}\rfloor ans=pmin(n,m)f(1)=pmin(n,m)d=1min(n,m)μ(d)d×pnd×pm
    如果止步于此,获得的只有美丽的黑色

    k = d × p k=d\times p k=d×p,则 p = k / d p=k/d p=k/d
    ⇒ a n s = ∑ k m i n ( n , m ) ⌊ n k ⌋ ⌊ m k ⌋ ∑ p ∣ k μ ( k p ) \Rightarrow ans=\sum_{k}^{min(n,m)}\lfloor{\frac{n}{k}}\rfloor\lfloor{\frac{m}{k}}\rfloor\sum_{p|k}\mu(\frac{k}{p}) ans=kmin(n,m)knkmpkμ(pk)

    最后就只剩下对 ∑ p ∣ k μ ( k p ) \sum_{p|k}\mu(\frac{k}{p}) pkμ(pk)进行前缀和的处理
    这里的处理略微不同于上一道题
    可以通过暴力枚举质因子,对质因子的倍数进行 μ \mu μ的累加,再前缀和处理出来
    在这里插入图片描述

    • code
      遇得到哦🙄
      define int long long让我直接慢了1s多,导致 T T T了,只能老老实实改long long才能顺利 A C AC AC
    #include <cstdio>
    #include <iostream>
    using namespace std;
    #define maxn 10000005
    int T, cnt;
    int sum[maxn], mu[maxn], prime[maxn];
    long long pre[maxn];
    bool vis[maxn];
    
    void init( int n ) {
    	mu[1] = 1;
    	for( int i = 2;i <= n;i ++ ) {
    		if( ! vis[i] ) prime[++ cnt] = i, mu[i] = -1;
    		for( int j = 1;j <= cnt && i * prime[j] < maxn;j ++ ) {
    			vis[i * prime[j]] = 1;
    			if( i % prime[j] == 0 ) {
    				mu[i * prime[j]] = 0;
    				break;
    			}
    			mu[i * prime[j]] = -mu[i];
    		}
    	}
    	for( int j = 1;j <= cnt;j ++ )
    		for( int i = 1;i * prime[j] <= n;i ++ )
    			sum[prime[j] * i] += mu[i];
    	for( int i = 1;i < maxn;i ++ ) pre[i] = pre[i - 1] + sum[i];
    }
    
    int main() {
    	init( 1e7 );
    	scanf( "%d", &T );
    	int n, m, r;
    	long long ans;
    	while( T -- ) {
    		scanf( "%d %d", &n, &m );
    		if( n > m ) swap( n, m );
    		ans = 0;
    		for( int i = 1;i <= n;i = r + 1 ) {
    			r = min( n / ( n / i ), m / ( m / i ) );
    			ans += 1ll * ( pre[r] - pre[i - 1] ) * ( n / i ) * ( m / i );
    		}
    		printf( "%lld\n", ans );
    	}
    	return 0;
    }
    

    [SDOI2014]数表

    • solution

    一句话题意,令 s u m ( i ) sum(i) sum(i)表示 i i i的因子和,给定 n , m , a n,m,a n,m,a,求🍔
    ∑ 1 ≤ i ≤ n , 1 ≤ j ≤ m s u m ( g c d ( i , j ) ) ≤ a s u m ( g c d ( i , j ) ) \sum_{1\le i\le n,1\le j\le m}^{sum(gcd(i,j))\le a}sum(gcd(i,j)) 1in,1jmsum(gcd(i,j))asum(gcd(i,j))

    先思考此题的弱化版,即不考虑 a a a
    ∑ i = 1 n ∑ j = 1 m s u m ( g c d ( i , j ) ) \sum_{i=1}^n\sum_{j=1}^msum(gcd(i,j)) i=1nj=1msum(gcd(i,j))
    F ( i ) F(i) F(i)表示 1 ≤ x ≤ n , 1 ≤ y ≤ m , i ∣ g c d ( x , y ) 1\le x\le n, 1\le y\le m,i|gcd(x,y) 1xn,1ym,igcd(x,y)的数对个数
    f ( i ) f(i) f(i)表示 1 ≤ x ≤ n , 1 ≤ y ≤ m , g c d ( x , y ) = i 1\le x\le n,1\le y\le m,gcd(x,y)=i 1xn,1ym,gcd(x,y)=i的数对个数
    则有
    F ( i ) = ∑ i ∣ d f ( d ) , F ( i ) = ⌊ n i ⌋ ⌊ m i ⌋ F(i)=\sum_{i|d}f(d),F(i)=\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor F(i)=idf(d),F(i)=inim
    莫比乌斯反演
    f ( i ) = ∑ i ∣ d μ ( d i ) F ( d ) = ∑ i ∣ d μ ( d i ) ⌊ n d ⌋ ⌊ m d ⌋ f(i)=\sum_{i|d}\mu(\frac{d}{i})F(d)=\sum_{i|d}\mu(\frac{d}{i})\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor f(i)=idμ(id)F(d)=idμ(id)dndm
    于是,有
    a n s = ∑ i = 1 m i n ( n , m ) s u m ( i ) f ( i ) ans=\sum_{i=1}^{min(n,m)}sum(i)f(i) ans=i=1min(n,m)sum(i)f(i) = ∑ i = 1 m i n ( n , m ) s u m ( i ) ∑ i ∣ d μ ( d i ) ⌊ n d ⌋ ⌊ m d ⌋ =\sum_{i=1}^{min(n,m)}sum(i)\sum_{i|d}\mu(\frac{d}{i})\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor =i=1min(n,m)sum(i)idμ(id)dndm = ∑ d = 1 m i n ( n , m ) ⌊ n d ⌋ ⌊ m d ⌋ ∑ i ∣ d s u m ( i ) μ ( d i ) =\sum_{d=1}^{min(n,m)}\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor\sum_{i|d}sum(i)\mu(\frac{d}{i}) =d=1min(n,m)dndmidsum(i)μ(id)
    如果现在知道 ∑ i ∣ d s u m ( i ) μ ( d i ) \sum_{i|d}sum(i)\mu(\frac{d}{i}) idsum(i)μ(id),就可以 O ( s q r t n ) O(sqrt{n}) O(sqrtn)的计算出答案
    s u m ( i ) sum(i) sum(i)可以线性筛得到,与上一题类似,枚举 i i i暴力更新倍数,前缀和即可, O ( l o g n ) O(logn) O(logn)

    现在加上限制 a a a,又怎么做呢??
    其实只有 s u m ( i ) ≤ a sum(i)\le a sum(i)a i i i才会产生贡献
    自然而然的想到,将 a , s u m ( i ) a,sum(i) a,sum(i)分别排序,树状数组维护
    本质就是树状数组在线插入
    在这里插入图片描述

    至于取模的问题,采取自然溢出的方式即可,具体细节可参见代码

    • code
    #include <cstdio>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    #define maxn 100000
    #define int long long
    struct node {
    	int n, m, a, id;
    }q[maxn], s[maxn];
    int prime[maxn], mu[maxn + 5], sum[maxn + 5], tree[maxn + 5], result[maxn + 5];
    bool vis[maxn + 5];
    int cnt;
    
    bool cmp( node x, node y ) {
    	return x.a < y.a;
    }
    
    void init() {
    	mu[1] = 1;
    	for( int i = 2;i <= maxn;i ++ ) {
    		if( ! vis[i] ) prime[++ cnt] = i, mu[i] = -1;
    		for( int j = 1;j <= cnt && i * prime[j] <= maxn;j ++ ) {
    			vis[i * prime[j]] = 1;
    			if( i % prime[j] == 0 ) {
    				mu[i * prime[j]] = 0;
    				break;
    			}
    			mu[i * prime[j]] = -mu[i];
    		}
    	}
    	for( int i = 1;i <= maxn;i ++ )
    		for( int j = i;j <= maxn;j += i ) sum[j] += i;
    	for( int i = 1;i <= maxn;i ++ )
    		s[i].a = sum[i], s[i].id = i;
    	sort( s + 1, s + maxn + 1, cmp );
    }
    
    int lowbit( int x ) {
    	return x & ( -x );
    }
    
    void add( int x, int v ) {
    	for( int i = x;i < maxn;i += lowbit( i ) )
    		tree[i] += v;
    }
    
    int query( int x ) {
    	int ans = 0;
    	for( int i = x;i;i -= lowbit( i ) )
    		ans += tree[i];
    	return ans;
    }
    
    int solve( int n, int m ) {
    	if( n > m ) swap( n, m );
    	int ans = 0, r;
    	for( int i = 1;i <= n;i = r + 1 ) {
    		r = min( n / ( n / i ), m / ( m / i ) );
    		ans += ( n / i ) * ( m / i ) * ( query( r ) - query( i - 1 ) );
    	}
    	return ans;
    }
    
    void Add( int id ) {
    	for( int i = 1;i * id <= maxn;i ++ )
    		add( i * id, mu[i] * sum[id] );
    }
    
    signed main() {
    	int Q;
    	scanf( "%lld", &Q );
    	for( int i = 1;i <= Q;i ++ )
    		scanf( "%lld %lld %lld", &q[i].n, &q[i].m, &q[i].a ), q[i].id = i;
    	sort( q + 1, q + Q + 1, cmp );
    	init();
    	int now = 0;
    	for( int i = 1;i <= Q;i ++ ) {
    		while( s[now + 1].a <= q[i].a && now < maxn ) Add( s[++ now].id );
    		result[q[i].id] = solve( q[i].n, q[i].m );
    	}
    	int mod = 1ll << 31;
    	for( int i = 1;i <= Q;i ++ )
    		printf( "%lld\n", result[i] % mod );
    	return 0;
    }
    

    [国家集训队]Crash的数字表格/JZPTAB

    • solution
      一句话题意,求🍔 ∑ i = 1 n ∑ j = 1 m l c m ( i , j ) \sum_{i=1}^n\sum_{j=1}^mlcm(i,j) i=1nj=1mlcm(i,j)
    • s t e p 1 : step1: step1: 枚举最大公因数

    = ∑ d = 1 m i n ( n , m ) ∑ i = 1 n ∑ j = 1 m i × j d =\sum_{d=1}^{min(n,m)}\sum_{i=1}^n\sum_{j=1}^m\frac{i\times j}{d} =d=1min(n,m)i=1nj=1mdi×j

    • s t e p 2 : step2: step2: 将最大公因数提到前面,循环上界压缩

    = ∑ d = 1 m i n ( n , m ) ∑ i = 1 ⌊ n d ⌋ ∑ j = 1 ⌊ m d ⌋ i × d × j × d d = ∑ d = 1 m i n ( n , m ) d ∑ i = 1 ⌊ n d ⌋ ∑ j = 1 ⌊ m d ⌋ i × j            [ g c d ( i , j ) = 1 ] =\sum_{d=1}^{min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\frac{i\times d\times j\times d}{d}=\sum_{d=1}^{min(n,m)}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}i\times j\ \ \ \ \ \ \ \ \ \ [gcd(i,j)=1] =d=1min(n,m)i=1dnj=1dmdi×d×j×d=d=1min(n,m)di=1dnj=1dmi×j          [gcd(i,j)=1]

    • s t e p 3 : step3: step3: 利用 ∑ i ∣ n μ ( i ) = [ n = 1 ] \sum_{i|n}\mu(i)=[n=1] inμ(i)=[n=1],对原式不会造成改变

    = ∑ d = 1 m i n ( n , m ) d ∑ i = 1 ⌊ n d ⌋ ∑ j = 1 ⌊ m d ⌋ ∑ k ∣ g c d ( i , j ) μ ( k ) × i × j =\sum_{d=1}^{min(n,m)}d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{k|gcd(i,j)}\mu(k)\times i\times j =d=1min(n,m)di=1dnj=1dmkgcd(i,j)μ(k)×i×j

    • s t e p 4 : step4: step4: 也将 μ \mu μ提到前面,那么为了保证 k ∣ i , k ∣ j k|i,k|j ki,kj,枚举 i , j i,j i,j变为直接枚举 k i , k j ki,kj ki,kj

    = ∑ d = 1 m i n ( n , m ) d ∑ k m i n ( ⌊ n d ⌋ , ⌊ m d ⌋ ) ∑ k i ⌊ n d ⌋ ∑ k j ⌊ m d ⌋ μ ( k ) × k 2 × i × j =\sum_{d=1}^{min(n,m)}d\sum_{k}^{min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}\sum_{ki}^{\lfloor\frac{n}{d}\rfloor}\sum_{kj}^{\lfloor\frac{m}{d}\rfloor}\mu(k)\times k^2\times i\times j =d=1min(n,m)dkmin(dn,dm)kidnkjdmμ(k)×k2×i×j

    • s t e p 5 : step5: step5: k k k提出来

    = ∑ d = 1 m i n ( n , m ) d ∑ k m i n ( ⌊ n d ⌋ , ⌊ m d ⌋ ) μ ( k ) × k 2 ∑ i = 1 ⌊ n d × k ⌋ ∑ j = 1 ⌊ m d × k ⌋ i × j =\sum_{d=1}^{min(n,m)}d\sum_{k}^{min(\lfloor\frac{n}{d}\rfloor, \lfloor\frac{m}{d}\rfloor)}\mu(k)\times k^2\sum_{i=1}^{\lfloor\frac{n}{d\times k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d\times k}\rfloor}i\times j =d=1min(n,m)dkmin(dn,dm)μ(k)×k2i=1d×knj=1d×kmi×j
    在这里插入图片描述

    ⚡:
    ∑ k m i n ( ⌊ n d ⌋ , ⌊ m d ⌋ ) μ ( k ) × k 2 \sum_{k}^{min(\lfloor\frac{n}{d}\rfloor, \lfloor\frac{m}{d}\rfloor)}\mu(k)\times k^2 kmin(dn,dm)μ(k)×k2使用老套路前缀和优化,之后 O ( 1 ) O(1) O(1)查询
    ∑ i = 1 ⌊ n d × k ⌋ ∑ j = 1 ⌊ m d × k ⌋ i × j \sum_{i=1}^{\lfloor\frac{n}{d\times k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d\times k}\rfloor}i\times j i=1d×knj=1d×kmi×j其实就是一个等差数列求积

    ∑ i = 1 n ∑ j = 1 m i × j = n × ( n + 1 ) 2 . m × ( m + 1 ) 2 \sum_{i=1}^n\sum_{j=1}^mi\times j=\frac{n\times (n+1)}{2}. \frac{m\times (m+1)}{2} i=1nj=1mi×j=2n×(n+1).2m×(m+1)

    • code
    #include <cstdio>
    #include <iostream>
    using namespace std;
    #define int long long
    #define mod 20101009
    #define maxn 10000005
    int mu[maxn], prime[maxn], sum[maxn];
    bool vis[maxn];
    int cnt, inv;
    
    void init() {
    	mu[1] = 1;
    	for( int i = 2;i < maxn;i ++ ) {
    		if( ! vis[i] ) prime[++ cnt] = i, mu[i] = -1;
    		for( int j = 1;j <= cnt && i * prime[j] < maxn;j ++ ) {
    			vis[i * prime[j]] = 1;
    			if( i % prime[j] == 0 ) {
    				mu[i * prime[j]] = 0;
    				break;
    			}
    			mu[i * prime[j]] = -mu[i];
    		}
    	}
    	for( int i = 1;i < maxn;i ++ )
    		sum[i] = ( sum[i - 1] + i % mod * i % mod * mu[i] % mod + mod ) % mod;
    }
    
    int seq( int n ) {
    	return n % mod * ( n + 1 ) % mod * inv % mod;
    }
    
    int calc( int n, int m ) {
    	if( n > m ) swap( n, m );
    	int ans = 0, r;
    	for( int i = 1;i <= n;i = r + 1 ) {
    		r = min( n / ( n / i ), m / ( m / i ) );
    		ans = ( ans + ( sum[r] - sum[i - 1] + mod ) % mod * seq( n / i ) % mod * seq( m / i ) % mod ) % mod;
    	}
    	return ans;
    }
    
    int qkpow( int x, int y ) {
    	int ans = 1;
    	while( y ) {
    		if( y & 1 ) ans = ans * x % mod;
    		x = x * x % mod;
    		y >>= 1;
    	}
    	return ans;
    }
    
    signed main() {
    	init();
    	inv = qkpow( 2, mod - 2 );
    	int n, m;
    	scanf( "%lld %lld", &n, &m );
    	int ans = 0;
    	for( int d = 1;d <= min( n, m );d ++ )
    		ans = ( ans + d * calc( n / d, m / d ) % mod ) % mod;
    	printf( "%lld\n", ans );
    	return 0;
    } 
    

    [SDOI2015]约数个数和

    • solution
      一句话题意,设 d ( x ) d(x) d(x)表示 x x x的约数和,求🍔

    ∑ i = 1 n ∑ j = 1 m d ( i × j ) \sum_{i=1}^n\sum_{j=1}^md(i\times j) i=1nj=1md(i×j)

    首先有一个约数和的公式🍔 我不是很会证
    在这里插入图片描述
    d ( i × j ) = ∑ x ∣ i ∑ y ∣ j [ g c d ( x , y ) = 1 ] d(i\times j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1] d(i×j)=xiyj[gcd(x,y)=1]

    = ∑ i = 1 n ∑ j = 1 m ∑ x ∣ i ∑ y ∣ j [ g c d ( x , y ) = 1 ] =\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[gcd(x,y)=1] =i=1nj=1mxiyj[gcd(x,y)=1]
    转换一下枚举方式,考虑直接枚举因子
    = ∑ i = 1 n ∑ j = 1 m ⌊ n i ⌋ ⌊ m j ⌋    ( g c d ( i , j ) = 1 ) =\sum_{i=1}^n\sum_{j=1}^m\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor\ \ (gcd(i,j)=1) =i=1nj=1minjm  (gcd(i,j)=1)
    F ( i ) F(i) F(i)表示 1 ≤ x ≤ n , 1 ≤ y ≤ m , i ∣ g c d ( x , y ) 1\le x\le n,1\le y\le m,i|gcd(x,y) 1xn,1ym,igcd(x,y)的约数和
    f ( i ) f(i) f(i)表示 1 ≤ x ≤ n , 1 ≤ y ≤ m , i = g c d ( x , y ) 1\le x\le n,1\le y\le m,i=gcd(x,y) 1xn,1ym,i=gcd(x,y)的约数和, f ( 1 ) f(1) f(1)即为最终答案
    F ( p ) = ∑ p ∣ d f ( d ) , F ( p ) = ∑ i = 1 ⌊ n p ⌋ ∑ j = 1 ⌊ m p ⌋ ⌊ n i ∗ p ⌋ ⌊ m j ∗ p ⌋ F(p)=\sum_{p|d}f(d),F(p)=\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}\lfloor\frac{n}{i*p}\rfloor\lfloor\frac{m}{j*p}\rfloor F(p)=pdf(d),F(p)=i=1pnj=1pmipnjpm
    莫比乌斯反演
    f ( p ) = ∑ p ∣ t μ ( t p ) F ( t ) = ∑ p ∣ t μ ( t p ) ∑ i = 1 ⌊ n t ⌋ ∑ j = 1 ⌊ m t ⌋ ⌊ n i ∗ t ⌋ ⌊ m j ∗ t ⌋ f(p)=\sum_{p|t}\mu(\frac{t}{p})F(t)=\sum_{p|t}\mu(\frac{t}{p})\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{t}\rfloor}\lfloor\frac{n}{i*t}\rfloor\lfloor\frac{m}{j*t}\rfloor f(p)=ptμ(pt)F(t)=ptμ(pt)i=1tnj=1tmitnjtm
    最后想求的答案就是 f ( 1 ) f(1) f(1)
    = ∑ t = 1 m i n ( n , m ) μ ( t ) F ( t ) , F ( t ) = ∑ i = 1 ⌊ n t ⌋ ∑ j = 1 ⌊ m t ⌋ ⌊ n i t ⌋ ⌊ m j t ⌋ =\sum_{t=1}^{min(n,m)}\mu(t)F(t),F(t)=\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{t}\rfloor}\lfloor\frac{n}{it}\rfloor\lfloor\frac{m}{jt}\rfloor =t=1min(n,m)μ(t)F(t),F(t)=i=1tnj=1tmitnjtm
    在这里插入图片描述

    对于求 F ( t ) F(t) F(t)的方法,先计算出 S ( t ) = ∑ i = 1 t ⌊ t i ⌋ S(t)=\sum_{i=1}^t\lfloor\frac{t}{i}\rfloor S(t)=i=1tit,则可以 O ( 1 ) O(1) O(1)得到

    • code
    #include <cstdio>
    #include <iostream>
    using namespace std;
    #define int long long
    #define maxn 50005
    int T, n, m, cnt;
    int mu[maxn], prime[maxn], sum[maxn];
    bool vis[maxn];
    
    void init() {
    	mu[1] = 1;
    	for( int i = 2;i < maxn;i ++ ) {
    		if( ! vis[i] ) prime[++ cnt] = i, mu[i] = -1;
    		for( int j = 1;j <= cnt && i * prime[j] < maxn;j ++ ) {
    			vis[i * prime[j]] = 1;
    			if( i % prime[j] == 0 ) {
    				mu[i * prime[j]] = 0;
    				break;
    			}
    			mu[i * prime[j]] = -mu[i];
    		}
    	}
    	for( int i = 1;i < maxn;i ++ ) mu[i] += mu[i - 1];
    	for( int x = 1;x < maxn;x ++ ) {
    		int ans = 0;
    		for( int i = 1, j;i <= x;i = j + 1 ) {
    			j = x / ( x / i );
    			ans += ( j - i + 1 ) * ( x / i );
    		}
    		sum[x] = ans;
    	}
    }
    
    int calc( int n, int m ) {
    	if( n > m ) swap( n, m );
    	int ans = 0, r;
    	for( int i = 1;i <= n;i = r + 1 ) {
    		r = min( n / ( n / i ), m / ( m / i ) );
    		ans += ( mu[r] - mu[i - 1] ) * sum[n / i] * sum[m / i];
    	}
    	return ans;
    }
    
    signed main() {
    	init();
    	scanf( "%lld", &T );
    	while( T -- ) {
    		scanf( "%lld %lld", &n, &m );
    		printf( "%lld\n", calc( n, m ) );
    	}
    	return 0;
    }
    
    展开全文
  • 反演

    2020-03-18 19:42:49
    线性离散反演 线性离散变换都可以表示为矩阵的形式 对于数列A[a0,a1...]A[a_0,a_1...]A[a0​,a1​...],B[b0,b1...]B[b_0,b_1...]B[b0​,b1​...],矩阵MMM满足B=MAB=MAB=MA,A=M−1BA=M^{-1}BA=M−1B,则变换MMM与...
  • 根据莫比乌斯函数性质, [ g c d ( i , j ) = 1 ] [gcd(i,j) = 1] [ g c d ( i , j ) = 1 ] 可以替换成: ∑ d ∣ g c d ( i , j ) μ ( d ) \sum_{d | gcd(i,j)}\mu(d) ∑ d ∣ g c d ( i , j ) ​ μ ( d ) ,整个...
  • 题目 ...思路 观察发现,题目要求我们求的就是 Σi=1nΣj=1m2∗(i,j)−1\Sigma_...于是我们开始反演: =Σd=1max(n,m)dΣi=1ndΣj=1md[(i,j)=1]=\Sigma_{d=1}^{max(n,m)}d\Sigma_{i=1}^{\frac{n}{d}}\Sigma_{j=1}^{\frac{m
  • 莫比乌斯反演

    2019-07-09 21:10:38
    莫比乌斯反演 (PS:在评论区中众多dalao的催促下,我认真的写了三天三夜写完了这篇杜教筛,保证是精品!) 前言 (这大概是我第一次写学习笔记吧OvO) 可能每一个刚开始接触莫比乌斯反演的OIer,起初都会厌恶这...
  • Mobius反演(莫比乌斯反演

    千次阅读 2018-07-16 16:00:36
    函数,它有如下的常见性质:    (1)对任意正整数 有          (2)对任意正整数 有       线性筛选求莫比乌斯反演函数代码。 void Init() { memset(vis,0,sizeof(vis)); mu...
  • 为提高频率域反演的分辨率和抗噪能力,减小频率域反演对初始模型的依赖程度,...最后,实际资料表明该方法能够稳定的从叠前地震数据中获取与测井数据相吻合的高分辨率弹性参数信息,并可有效的运用到储层含油气性质检测中。
  • n,p,qn,p,qn,p,q 均为 10710^7107,这个规模下可以考虑求出所有的 f(i)f(i)f(i),题目给出的式子很明显要用莫比乌斯反演,因为莫比乌斯反演的形式为: 形式一:设F(n)=∑d∣nf(d)F(n) = \displaystyle\sum_{d | n} f...
  • 为了提高波阻抗反演的分辨率,在密度资料对反演结果产生重要影响的基础上,利用岩心、测井及地震资料,从岩石物理性质一测井响应一地震响应角度分析,提出应用测井一地震多属性密度曲线重构技术合成拟密度曲线,其...
  • 浅谈各种反演

    2020-05-10 18:37:16
    反演好神奇啊 就像 膜 魔法一样 反演在OI界还是一个非常常用的一个东西,觉得还是写个总结好一点 前置知识 二项式定理 : (证明可通过数学归纳法) 正文 定义 何为反演 ? 我是通俗理解为已知 A 求 B为正演, 那...
  • 本人也学识浅薄,姑且讲一下我对于圆反演的一些皮毛之见。 首先我们要明白反演是什么: 反演是一种基本的几何变换。给定一个平面上的一个反演中心$O$和一个常数$k$,对于任意一个点$A(A \neq O)$,我们可以找到一...
  • 考虑地应力作用下节理扩展引起的煤岩物理力学性质改变,进而导致煤层应力、变形的重新分布,给出了煤岩单元节理扩展的计算方法,并分析了节理扩展与应力的相互作用关系。应用小波神经网络方法及逐级加载算法,提出节理...
  • 莫比乌斯反演的两种形式及其证明

    千次阅读 2018-07-28 13:52:55
    莫比乌斯反演形式一:     证明: 把 代入右边的式子,得:   根据莫比乌斯函数的性质,有定理:   因此,只有...
  • 地震反演概念与分类

    千次阅读 2019-07-08 18:09:39
    其作用原理是利用地表观测的地震资料,对地下层空间结构和物理性质进行成像分析的过程。 地震反演的目的是由已知观测数据通过计算分析得到地下介质模型,从而有效做出预测,提高生产工作效率。在探井井位探测中,井...
  • 莫比乌斯反演详解

    千次阅读 2020-01-29 22:18:12
    这里先给出莫比乌斯反演公式:   f ( n ) = ∑ d ∣ n μ ( d ) F ( n d ) f(n) = \sum\limits_{d|n}μ(d)F(\frac{n}{d}) f ( n ) = d ∣ n ∑ ​ μ ( d ) F ( d n ​ ) 其他形式:  ​ f ( n ) = ∑ n ∣ d ...
  • 莫比乌斯反演入门

    2019-11-06 16:26:55
    其实莫比乌斯反演就只有两个重要的公式,而且用到的最多的也只有一个(其实都差不多),但是需要一些预备知识。 莫比乌斯函数,质数线性筛,整除分块,积性函数以及一些其他的数论知识,下面会将其中一部分重要的...
  • 莫比乌斯反演—详解

    千次阅读 2016-05-27 19:11:51
    1、莫比乌斯反演是组合数学中很重要的内容,可以用于解决很多组合数学的问题。 2、莫比乌斯反演是数论中的重要内容,在许多情况下能够简化运算。 3、是个个很神奇的东西。 引入 考虑以下求和函数 fn=∑d|ngdf_n...
  • 基于三维地应力场反演技术开展了相关研究,并以集贤煤矿西二采区为研究对象,在地质构造特征分析、煤岩物理力学性质和矿井地应力实测的基础上,根据多元线性回归原理对三维地应力场进行数值模拟反演,获得了研究区域...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,327
精华内容 1,330
关键字:

反演性质