1.莫比乌斯反演(宋新波1.28上午)

莫比乌斯反演中山纪念中学宋新波1WC2016绵阳南山例1.[HAOI2011]Problemb的个数。满足要求的数对行，每行一个整数表示共。表示行每行五个整数，分别接下来第一行一个整数的最大公约数。和函数为且满足每次求有多少个数对个询问对于给出的),(,,,,,,gcd,,gcd,,),,(,yxTkdcbaTTyxyxkyxdycbxayxT输出格式：输入格式：题目描述：25151151522样例输入：314样例输出：500001,500001,500001,500001:%100100001,100001,100001,10001:%7010001,10001,10001,10001:%501001,1001,1001,1001:%20kdcbaTkdcbaTkdcbaTkdcbaT数据范围：2WC2016绵阳南山例1.[HAOI2011]Problemb3分。，预计得分询问的时间复杂度为即可。是否等于，判断枚举，，同理得得则：令以上方法可以优化其中为单次询问的时间复杂度是否等于，判断中的每一个数再枚举中的每一个数枚举：20)ln(1)','gcd(',''''*,'*,'*,),(ln,),gcd(,,,2kknnmTOyxyxkdykckbxkabxkaykyxkxcdmabnnnmOkyxydcxba算法一WC2016绵阳南山例1.[HAOI2011]Problemb4的数”中含有因子到表示“用的互异质因子是设互质的数的个数，则中与到等于设是否等于判断，的每一个数到再枚举中的每一个数到时，先枚举计算原问题的答案则且满足表示有多少个数对设：pAppppiiiknxkmxtaaaxxfmnAnsxkmxfyxykmxknmnAnscaAnscbAnsdaAnsdbAnskyxmynxyxmnAnst1*...*2*1,11),gcd(1,1,1,11,,1,,,gcd1,1,,211算法二WC2016绵阳南山例1.[HAOI2011]Problemb5分。，此方法预计得分最多为这里的，的数据对于题目的质因子的个数。为，的时间复杂度为计算时，如利用容斥原理得：：504)(,1000231011*7*5*3*21000,,%50)(265*3*21005*31005*21003*2100510031002100100305*3*2100,30*...**.........21111...11...121111121212121xgdbxxgOxffxkmxiiiiiikmkmiiiiiikmkmkmxfxgtrtrtrtrttkjitkjitjijitiitiirrrrpppAAAAAAAAAAAAA算法二WC2016绵阳南山例1.[HAOI2011]Problemb分。。可以得单次询问的时间复杂度，其中由此得：所以的个数就是答案。的数对合的求解是很容易的，符的个数的数对且表示设很难。直接计算可以先进行交换。如果的个数，假设的数对且表示设50ln*1,1*****),(11*,11**,),(,gcd1,1)(,),(,gcd1,1)(12111knikinjkndknknOkinknijikfikgikfkmknkgyxkmykyknxkxkgdkfkgyxyxkmynxkgkfmnmnyxkyxmynxkfyx:算法三6WC2016绵阳南山例1.[HAOI2011]Problemb7怎么解决？怎么解决？500001,500001,500001,500001:%100100001,100001,100001,10001:%70kdcbaTkdcbaTWC2016绵阳南山一、莫比乌斯反演的引入nddgnfngnf的两个函数，并满足：是定义在正整数集合上和12643211211111105211093198421871763216515421431321211ggggggfggfggggfgggfggggfggfggggfggfgggfggfggfgf道：根据定义，我们可以知24612121111112510103994881771236615524413312211ffffgffgffffgffgffgffgffffgffgffgffgffgfg：n推出gn根据f观察左边的等式，可以8WC2016绵阳南山一、莫比乌斯反演的引入24612121111112510103994881771236615524413312211ffffgffgffffgffgffgffgffffgffgffgffgffgfg继续观察下面的式子：?*nddfng以下规律：观察左边的等式，发现ndndndddnfngddnfngdnddndfngdndndn*'*','*,d'也可以写成：令则：对应的某函数值，记为是有关系，与没有直接的关系，而是上面的？部分与:继续观察发现9WC2016绵阳南山二、莫比乌斯反演ndndddnfngdgnf*公式：012,111,110,09,08,1716,15,04,13,12,11的值如下：d部分μ观察前面的例子，发现031*...**21,11121ddkidddkikpppp其余情况为互异的素数，则，其中若则若如下：为莫比乌斯函数，定义dμ10WC2016绵阳南山三、莫比乌斯函数的性质1,01,1nnndnd若若，有：：对于任意正整数性质一。所以，个。有，这样的，则对应的且质因子的指数为的互异质因子，个中含有的情况，假设或我们只需考虑对应的时，，当存在某一个其中设的互异质因子。为其中时，设，成立；时，0*110,0210,*...*2*11,*...*2*1121111111102121krkrrkndrkriiiiindCCyyxypppppppdddnrddkikyyydnkikxxxnndnkk证明：11WC2016绵阳南山三、莫比乌斯函数的性质是积性函数莫比乌斯函数n性质二：。，则称它为完全积性的不互质，也有就算若对于某积性函数函数。在数论上就称它为积性互质时当若的一个算术函数于正整数数论中的积性函数：对、陪域为复数的函数。数，指定义域为正整数算术函数：又称数论函bfafabfbanfbfafabfbafnfn,,,,,11,kiipppppixnnkikxxxnnbaabnbabaik11,*...*2*1,,,,)2(111n)1(21则有的互异质因子为其中设是积性函数易知：的定义中的三种情况时分别取互质时，让当时，当证明：12WC2016绵阳南山四、莫比乌斯函数的计算end;end;-mu[i];:mu[t]end;break;0;:mu[t]beginthen0prime[j]modiiffalse;:flag[t]break;maxnthentifprime[j];*i:tbegindoprime[0]to1:jforend;-1;:mu[i]i;:e[0]]prime[prim0]);inc(prime[beginthenflag[i]ifbegindonto2:ifor1;:mu[1]0;:prime[0]true);g),sizeof(flalag,fillchar(f内完成。性筛法在是积性函数，可以用线由于nOn值只被计算了一次。且它们的莫比乌斯函数储起来，并之间的每个素数都被存到n2。杂度为只被更新一次，时间复，因此每一个数的也就没有在此处被计算的，是不可能枚举到素数循环，循环会中途退出，时，由于循环枚举到素数时，当而的值时，会计算当，互质，所以，由于，则有的质因子的另一个大于的最小质因子为设合数被计算了一次。数的莫比乌斯函数值只这段代码保证了每个合nOtqjtppjititpqpqptqptptptttttt22,**,*,2121113WC2016绵阳南山五、莫比乌斯反演的证明ndndddnfngdgnf*证明：。得证！综上：，的约数时，取小于当，时，当的值，考虑若若，有质一：对于任意正整数根据莫比乌斯函数的性为主体的等价形式以为主体的，接下来考虑该式是以证明：ngddnfngdigdningdigdnidnnddigdigigdigdddnfngndindindindindindndindnindinidnindnd*00211:1,01,1n**14WC2016绵阳南山六、莫比乌斯反演的变形iddfigdgifdidfigidgifnddinddiindind,,11**写法二：写法一：变形：。得证！综上，，时，当，时，当性质一有：，根据莫比乌斯函数的上式则有：令：igdiTgdidfdiTgdTigdiTgdTdiTgTddidgddidfiginTTdindT