|
定義 對于此篇博客的一些同樣的定義，在此給出： \(a|b\)表示\(a\%b=0\)，\(a⊥b\)表示\(gcd(a,b)=1\)，\([P]\)表示的是當\(P\)為真時，值為\(1\)，\(P\)為假時，值為\(0\)。 且對于下面的文章，兩個數(shù)論函數(shù)\(f,g\)的狄利克雷卷積形式寫成\(f*g\)。 狄利克雷卷積以及各種性質(zhì)數(shù)論函數(shù)卷積？ 卷積難道不是這樣的形式嗎（這里的\(f(n)\)表示的是次數(shù)為\(n\)的系數(shù)）： \(f(n)=\sum\limits_{i=0}^{n}a(i)b(n-i)\) 當然，這是普通卷積，適用于所有函數(shù)。 而狄利克雷卷積不一樣，他是作用于數(shù)論函數(shù)的。 數(shù)論函數(shù)是什么呢？就是定義域在正整數(shù)域，值域在實數(shù)域的函數(shù)。 比如斐波那契數(shù)列、\(φ\)等。 形式對于三個數(shù)論函數(shù)（\(f(n)\)表示的是第\(n\)項的值）： \(f(n)=\sum\limits_{d|n}a(d)b(\frac{n}cyac7f7)\) 這個形式就是狄利克雷卷積形式。 性質(zhì)
積性函數(shù)也許你經(jīng)常會看到某某某函數(shù)為完全積性函數(shù)。 但是卻不知道他是什么，對吧。 這里我們給出定義： 當\(f\)是數(shù)論函數(shù)且\(x⊥y\)時\(f(xy)=f(x)f(y)\)，那么\(f\)就是積性函數(shù)。 性質(zhì)1當\(f\)是積性函數(shù)時，\(f(1)=1\)否則\(f\)的值全部為\(0\)。 證明：如果\(f(x)\)的值不為\(0\)，且\(f(1)≠1\)，因為\(f(1)*f(1)=f(1)\)，所以\(f(1)=0\)，而\(f(x)*f(1)=f(x)\)，當\(f(x)>0\)且\(f(1)=0\)，則\(f(x)*f(1)=0\)，不成立，所以\(f(1)=1\)。 性質(zhì)2兩個積性函數(shù)的狄利克雷卷積也是積性函數(shù)。 下面證明來自咕咕日報（注意要利用到一個定理，就是：\(n⊥m,a|n,b|m\)，那么\(a⊥b\)）。 注：但是兩個完全積性函數(shù)的狄利克雷卷積不一定是完全積性函數(shù)。 一些完全積性函數(shù)這里我們給出一些常見的完全積性函數(shù)。 \(?\)函數(shù)，又叫單位元。 \(?(i)=[i=1]\)（也就是只有\(zhòng)(?(1)=1\)，其他都為\(0\)） （性質(zhì)：\(?*f=f\)，這個想想就知道了吧QMQ） \(id\)函數(shù)，\(id(i)=i\)。 \(1\)函數(shù)，\(1(i)=1\)。 逆函數(shù)逆函數(shù)也是數(shù)論函數(shù)。（理論上來講數(shù)論函數(shù)的除法就是乘上逆函數(shù)。） 對于一個數(shù)論函數(shù)\(f\)，其逆函數(shù)是\(g\)，那么\(f*g=?\)。 相當于數(shù)論函數(shù)中的逆元。 但是問題又來了，如何求逆函數(shù)呢？ 我們這里給出公式（還是咕咕日報的）： \(g(n)=\frac{1}{f(1)}([n=1]-\sum\limits_{i|n,i≠1}f(i)g(\frac{n}{i}))\) 可以理解為是一種遞推式。 把這個定義套進去： \(\sum\limits_{i|n}f(i)g(\frac{n}{i})\) \(=f(1)g(n) \sum\limits_{i|n,i≠1}f(i)g(\frac{n}{i})\) \(=[n=1]\) 其實可以證明一個函數(shù)的逆函數(shù)只有一個（下面的證明不包括那個全部為\(0\)的數(shù)論函數(shù)，那玩意沒有逆函數(shù)吧?。。AQ）。（應(yīng)該只有一個吧QAQ） 對于\(f(1)\)，\(g[1]\)是固定的，而對于\(g[1]\)~\(g[i-1]\)固定的話，\(g[i]\)也是固定的。（這個就是不用公式也可以明白吧。） 所以逆函數(shù)是固定唯一的。 性質(zhì)1積性函數(shù)的逆函數(shù)也是積性函數(shù)。 來自咕咕日報： 這里解釋一下。 他沒有證\(0\)函數(shù)（全部為\(0\)的那個函數(shù)，以后我們討論逆函數(shù)都不討論他）。 同時為什么他可以直接化成這個式子呢，因為除了\(0\)函數(shù)的積性函數(shù)的\(f(1)=1\)，而對于\(nm>1\)的情況，\([nm=1]\)肯定為\(0\)，所以直接化成了那個樣子。 莫比烏斯反演因子包含對于\(f\)函數(shù)，我們定義\(F=f*1\)，即 \(F(n)=\sum\limits_{i|n}f(i)\)。 那么\(f(n)=\sum\limits_{i|n}\mu(\frac{n}{i})*F(i)\)。 這就是因子包含的反演公式，你也許會覺得這個公式很廢柴，但是下面會講的。（這個公式其實是真的廢柴，反正我做了這么久的題目都很少套用這個，不過如果你不會這個的證明的話莫比烏斯反演還是有點難度的。） 狄利克雷卷積方式證明因子包含公式（適合較理性的同學證明）終于到了正題了。 我們定義\(\mu\)為\(1\)函數(shù)的逆。 那么\(g=f*1\)，那么就有\(zhòng)(f=f*1*\mu=g*\mu\)。 換成式子形式就是： \(f(n)=\sum\limits_{i|n}g(i)*\mu(\frac{n}{i})\) 證畢。 真的感覺狄利克雷卷積的證明方式簡單易懂。 楊輝三角形與容斥原理下面證明需要。 對于楊輝三角形第\(i\)行第\(j\)列就是\(f(i,j)\)，根據(jù)定義就是\(f(i,j)=f(i-1,f) f(i-1,j-1)\)，我們默認\(f(i,1)=f(i,i)=1\)。 我們發(fā)現(xiàn)其實\(f(i,j)=C_{i-1}^{j-1}\)。 用數(shù)學歸納法來證明，對于\(i-1\)行都滿足這個式子，那么\(i\)行滿不滿足？ \(C_{i-1}^{j} C_{i-1}^{j-1}=\frac{(i-1)!}{j!(i-j-1)!} \frac{(i-1)!}{(j-1)!(i-j)!}\) \(=\frac{(i-1)!(i-j)}{j!(i-j)!} \frac{(i-1)!j}{j!(i-j)!}=\frac{i!}{i!(i-j)!}=C_{i}^j\) 那么我們知道了楊輝三角形的性質(zhì)有什么用呢？ 對于楊輝三角形第\(i\)層，我們選出下標是奇數(shù)的，發(fā)現(xiàn)他們映射到上一層剛好覆蓋。 偶數(shù)的也一樣。 那么只要奇數(shù)項為\( \)，然后偶數(shù)項為\(-\)，一加就為\(0\)了。（除了三角形頂端） μ函數(shù)的定義根據(jù)逆函數(shù)的定義，我們易知\(\mu(1)=1,\mu(2)=-1,\mu(3)=-1...\)。 仔細觀察，\(\mu(i)\)當\(i\)為質(zhì)數(shù)時為\(-1\)，\(i=1\)時為\(1\)。 我們還要得到更普遍的定義。 仔細一看這個式子（\(n>1\)）： \(g(n)=-\sum\limits_{i|n,i≠1}g(\frac{n}{i})\) \(g(n)=-\sum\limits_{i|n,i≠n}g(i)\) 這個不就是查自己所有因子和\(1\)除自己以外的\(g\)值和的負數(shù)嗎。 那么有\(zhòng)(2\)質(zhì)數(shù)因子的就是\(1\)，那么\(3\)個質(zhì)數(shù)因子用容斥就可以知道是\(-1\)。 那么我們用數(shù)學歸納法來證明。 對于有\(zhòng)(i(i\%2=0)\)個質(zhì)數(shù)因子的數(shù)（假設(shè)前面的奇數(shù)個質(zhì)數(shù)因子的數(shù)都為\(-1\)，偶數(shù)個質(zhì)數(shù)因子的數(shù)都為\(1\)。） \(C_{i}^{0}-C_{i}^{1} C_{i}^{2}-C_{i}^{3} ...-C_{i}^{i-1}=(C_{i}^{0}-C_{i}^{1} C_{i}^{2}-C_{i}^{3} ...-C_{i}^{i-1} C_{i}^{i})-C_{i}^{i}=0-C_{i}^{i}=-1\) 反之偶數(shù)是\(1\)（因為偶數(shù)的話，最后一項是\(-\)，要\( \)回來）。 以上證明利用楊輝三角形性質(zhì)。 那么如果有的因子次數(shù)是\(2\)或以上呢，我們先證數(shù)字是質(zhì)數(shù)的二次冪的數(shù)字，如：\(p_0^{2}\)。 只有兩個因子：\(1,p_0\)，一加為\(0\)。 那么數(shù)學歸納法走起。 證明\(p_{0}^{i}=0\)，當\(p_{0}^{2}\)~\(p_0^{i-1}\)都是\(0\) 那么真實有效的就只有\(zhòng)(1\)和\(p_0\)，那么就是\(0\)啦。 證畢。 而且因為\(1\)是積性函數(shù)，所以\(\mu\)也是積性函數(shù)。 所以任何因子有質(zhì)數(shù)次冪的數(shù)字都可以表示為一個數(shù)字乘以質(zhì)數(shù)次冪。 那么也就都是\(0\)了。 至此，我們得到了\(\mu\)的值。 \(\mu(i)=\left\{\begin{matrix} 1（當i有奇數(shù)個質(zhì)數(shù)因子）\\ -1（當i有偶數(shù)個質(zhì)數(shù)因子）\\ 0（當i的某個質(zhì)數(shù)因子的質(zhì)數(shù)大于1） \end{matrix}\right.\) 容斥原理證明容斥原理證明原理有個缺陷就是很難推式子，但是證明正確性確實挺好的。 不過經(jīng)過這次證明我的容斥進步了不少 我們再把式子看一遍： \(F(n)=\sum\limits_{i|n}f(i)\) \(f(n)=\sum\limits_{i|n}\mu(\frac{n}{i})*F(i)\) 那么我們?nèi)莩饩褪峭ㄟ^容斥把\(F(n)\)中的\(f(n)\)保留，同時把\(f(i)(i≠n)\)全部刪去。 而我們繼續(xù)觀察下面的式子，這個式子我們再把其轉(zhuǎn)化一下： \(f(n)=\sum\limits_{i|n}\mu(i)*F(\frac{n}{i})\) 對于\(f(i)(i|n)\)，我們設(shè)\(\frac{n}{i}\)拆成\(p_0^{a_0}p_1^{a_1}...p_i^{a_i}\)（老樣子，\(p\)都是質(zhì)數(shù)），那么這個式子的本質(zhì)就是減去\(0\)個質(zhì)數(shù)的情況，加上\(1\)個質(zhì)數(shù)的情況，減去\(2\)個質(zhì)數(shù)的情況，加上\(3\)個質(zhì)數(shù)的情況，其實也就是討論\(p_0p_1p_2...p_i\)的這個數(shù)字，因為如果質(zhì)數(shù)質(zhì)數(shù)大于\(1\)的話\(\mu\)為\(0\)，所以其實是可以把指數(shù)去掉。 再仔細觀察式子不就是求\(f(i)\)的系數(shù)嗎，\(f(i)\)的系數(shù)加減可以看成是\(C_{i}^0-C_i^1 ...=0\)。 當然，有個例外，\(f(n)=C_0^0=1\)，所以證畢。 μ函數(shù)的性質(zhì)由于\(\mu*1=?\) \(\sum\limits_{i|n}\mu(i)=[n=1]\) 這個性質(zhì)十分重要！ 倍數(shù)包含\(F(i)=\sum\limits^{n}_{i|j}f(j)\) \(f(i)=\sum\limits^{n}_{i|j}\mu(\frac{j}{i})f(j)\) 這個你只要理解了因子包含的容斥證明就可以證了。 數(shù)論分塊對于\(\frac{n}{i}(1<=i<=n,i∈Z^ )\) 那么這個有多少取值呢。 可以證明最多\(2\left \lceil \sqrt{n} \right \rceil\)。 當\(i<\sqrt{n}\)，有\(zhòng)(\sqrt{n}\)個取值 而\(i=\sqrt{n},\frac{n}{i}=\sqrt{n}\)，所以\(i>=\sqrt{n}\)也只有\(zhòng)(\sqrt{n}\)個取值。 所以理論上\(\frac{n}{i}\)的值應(yīng)該有一段的\(i\)相同。 但是如果求出這一段的\(r\)呢？就是\(\left \lfloor\frac{n}{\left \lfloor \frac{n}{i} \right \rfloor}\right \rfloor\)。 我們可以證一下。 對于\(\left \lfloor \frac{n}{i} \right \rfloor\)，我們可以看成是找到最大的整數(shù)\(x\)滿足\(x*i<=n\)，同時\(\left \lfloor \frac{n}{x} \right \rfloor=i\) 為什么 對于\(x=\left \lfloor \frac{n}{i} \right \rfloor\)。 那么\((x 1)*i=x*i i\)，由于\(x=\left \lfloor \frac{n}{i} \right \rfloor\)，所以\(x*i<=n\)，且\(n-x*i<i\)，所以\((x 1)*i>n\)，所以\(\left\lfloor\frac{n}{x}\right\rfloor=i\) 那么對于我們要看\(\left \lfloor \frac{n}{i} \right \rfloor=y\)的最大的\(i\)，那么其實就可以化成\(\left \lfloor \frac{n}{y} \right \rfloor=i\)，也就是最大的\(i\)了，而且由上面的式子可以得到\(\left \lfloor \frac{n}{i 1} \right \rfloor<y\)。 所以就是\(\left \lfloor\frac{n}{\left \lfloor \frac{n}{i} \right \rfloor}\right \rfloor\) 那么這個有什么用后面的第一題就會講到了。 練習1我們發(fā)現(xiàn)\([a,b],[c,d]\)其實可以拆成四個區(qū)間。 \(([1,b],[1,d])-([1,a-1],[1,d])-([1,b],[1,c-1]) ([1,a-1],[1,c-1])\) 開始推公式吧。其實這應(yīng)該是例題來的 \(\sum\limits_{i=1}^\sum\limits_{j=1}^oswmmfr[gcd(i,j)=k]\) 我們整體除以\(k\)，那么就是 \(\sum\limits_{i=1}^{\frac{k}}\sum\limits_{j=1}^{\fracpm2u27i{k}}[gcd(i,j)=1]\) \(=\sum\limits_{i=1}^{\frac{k}}\sum\limits_{j=1}^{\fracpuo0ey7{k}}[gcd(i,j)=1]\) 咦后面那個是不是可以換成\(\mu\)函數(shù)呀。 \(=\sum\limits_{i=1}^{\frac{k}}\sum\limits_{j=1}^{\fracokutlpj{k}}\sum\limits_{t|gcd(i,j)}\mu(t)\) 那怎么求。 莫比烏斯反演推公式最重要的一步之一。 調(diào)換加法順序。 我們先設(shè)數(shù)字，不然有點難寫。 \(b’=\frac{k},d'=\fracos2ygjv{k}\)。 下面證明用\(b,d\)代替\(b',d'\)。 \(\sum\limits_{t=1}^{min(b,d)}\mu(t)(\sum\limits_{i=1}^{\frac{t}}\sum\limits_{j=1}^{\frac29d2iwp{t}}1)\) 我們突然發(fā)現(xiàn)后面的部分可以\(O(1)\)求出來， 但是前面循環(huán)怎么辦呢。 爆算豈不是\(O(n^2)\) 我們突然發(fā)現(xiàn)如果\(\frac{t},\frac4jw7tv2{t}\)不變，后面就不變，所以我們只要對\(\mu\)做一遍前綴和就行了。 而\(\frac{t},\fracsgishda{t}\)合起來也只有\(zhòng)(O(\sqrt{n})\)和取值。 所以時間復(fù)雜度就是\(O(n\sqrt{n})\) 其實即使不拆應(yīng)該也可以算，只不過應(yīng)該要處理\(ceil\)和\(floor\)，太麻煩了。。。 2那么這道題目又是什么意思，一開始我們以為很難，但是仔細一看，秒呀，原來\(1≤x,y≤n\)，原來是同一個數(shù)字呀。 注：\(prim\)是質(zhì)數(shù)集。 那么不就可以套用\(φ\)函數(shù)了嗎，\(φ(i)\)的定義是與\([1,i]\)內(nèi)與\(i\)互質(zhì)的數(shù)的個數(shù)。 化式子\((n<=m)\)。 \(\sum\limits_{d∈prim}^{n}\sum\limits_{i=1}^{\frac{n}z7motp8}\sum\limits_{j=1}^{\frac{n}h7o9lxl}[gcd(i,j)=1]\) 其實這個后面也有一道加強版 但是其實我們是可以用\(φ\)函數(shù)\(O(1)\)求出后面的數(shù)字，就是用\(φ\)做一遍前綴和\(g\)。 那么就是\(2g(\frac{n}hmx4wty)-1\)，后面那個\(-1\)是怎么回事呢，我們是把\((i,j)(i<j)\)擴展到了所有數(shù)對，但是\((1,1)\)不一樣啊。 所以我們可以爆枚素數(shù)。 不就是一遍線性篩的事情嗎。 \(O(n)\)。 3完全平方數(shù)？ 這道題目應(yīng)該是考你容斥的。 設(shè)\(i\)為\(p_0^{a_0}p_1^{a_1}p_2^{a_2}...p_i^{a_{i}}\)。 然后把\(a>1\)的提出來化成\(i\)的一個因子\(b_0^2,b_1^2b_2^2...b_j^2\)。 那么我們就是想讓統(tǒng)計區(qū)間內(nèi)提出來后因子為\(1\)的保留，因子大于\(1\)的消掉。 那么就是\(\sum\limits_{i=1}^{i^2<=n}\mu(i)\frac{n}{i^2}\)。 預(yù)處理\(\mu\)。 那么現(xiàn)在問題就是我們怎么知道\(n\)呢？二分枚舉出奇跡?。?！ 時間復(fù)雜度：\(O(T\sqrt{n}logn)\) 4這道題目我們還是繼續(xù)化簡式子（一下證明\(n≤m\)）。 \(\sum\limits_{t∈prim}^{n}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i,j)=d]\) \(\sum\limits_{t∈prim}^{n}\sum\limits_{i=1}^{\frac{n}efa2f9x}\sum\limits_{j=1}^{\frac{m}qmgqicq}\sum\limits_{k|gcd(i,j)}\mu(k)\) 調(diào)換順序 \(\sum\limits^{n}_{t∈prim}\sum\limits_{k=1}^{\frac{n}2ylktma}\mu(k)\sum\limits^{\frac{n}{kt}}_{i=1}\sum\limits^{\frac{m}{kt}}_{j=1}1\) 咦，后面的是不是可以\(O(1)\)算。 但是你是不是還是要枚舉\(t\)？看看多組數(shù)據(jù)，直接爆炸?。?！Boom！ 所以我們這里引入這種莫反的另外一個騷操作！ 設(shè)\(T=tk\)。 \(\sum\limits_{T=1}^{n}\sum\limits_{t∈prim,t|T}\mu(\frac{T}{t})\sum\limits_{i=1}^{\frac{n}{T}}\sum\limits_{j=1}^{\frac{n}{T}}1\) 這不是一樣嗎QAQ。 一樣嗎-_- \(\sum\limits_{T=1}^{n}\sum\limits_{i=1}^{\frac{n}{T}}\sum\limits_{j=1}^{\frac{n}{T}}\sum\limits_{t∈prim,t|T}\mu(\frac{T}{t})\) 原來能這么化嗎?。。。。。。。。?！ 我們只要預(yù)處理后面那個就行了?。。。?！ 而后面那個的話預(yù)處理應(yīng)該是差不多還行吧QAQ，我也不知道也。 不過應(yīng)該是接近一億的。 然后前面的數(shù)論分塊就行了。 時間復(fù)雜度\(O(? T\sqrt{n})\) 5好題。 一道很成功的將數(shù)論和數(shù)據(jù)結(jié)構(gòu)結(jié)合的題目（設(shè)\(n<=m\)）。 設(shè)\(d(i)\)為一個數(shù)字的約數(shù)和。 那么這個函數(shù)很明顯是\(id*1\)，所以是一個積性函數(shù)，可以用線性篩篩。 然后開始列式子，我們假設(shè)沒有\(zhòng)(a\)的限制。 \(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}d(gcd(i,j))\) \(\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{\frac{n}h2dvlwb}\sum\limits_{j=1}^{\frac{m}mqmvm49}d(d)[gcd(i,j)=1]\) \(\sum\limits_{d=1}^{n}d(d)\sum\limits_{i=1}^{\frac{n}vb72mag}\sum\limits_{j=1}^{\frac{m}c4xzh9w}\sum\limits_{k|gcd(i,j)}\mu(k)\) \(\sum\limits_{d=1}^{n}d(d)\sum\limits_{k=1}^{\frac{n}puwooro}\mu(k)\frac{n}{kd}*\frac{m}{kd}\) 我們再設(shè)\(T=kd\) \(\sum\limits_{T=1}^{n}\sum\limits_{k|T}d(\frac{T}{k})\mu(k)(\frac{n}{T})(\frac{m}{T})\) \(\sum\limits_{T=1}^{n}(\frac{n}{T})(\frac{m}{T})\sum\limits_{k|T}d(\frac{T}{k})\mu(k)\) 仔細一看，前面可以整除分塊了呢！??！ 但是后面QAQ。 由于我們需要數(shù)論分塊，我們需要后面這坨東西的前綴和。 但是我們發(fā)現(xiàn)，只有當\(\frac{T}{k}>=a\)的時候，\(d(\frac{T}{k})\mu(k)\)才可以造成影響。 所以我們應(yīng)當把詢問拿\(a\)排個序。 然后對于目前的\(a\)，暴力查哪個\(d\)又可以了（這個按\(d\)值排個序），然后繼續(xù)暴力隊可以更新的\(T\)拿去更新，時間復(fù)雜度：\(O(nlogn)\)，完美！??！ 不對，你前綴和怎么查。。。 所以我們用樹狀數(shù)組解決。 時間復(fù)雜度：\(O(Q\sqrt{n} nlog^2n)\)。 6下面都是默認\(n<=m\) 這道題目是\(lcm(i,j)\)？ 我有點慌張。 但是一想\(lcm(i,j)=\frac{ij}{gcd(i,j)}\)。 于是又開始做了起來。 \(\sum\limits_{d=1}^{n}\frac{1}obu877y\sum\limits_{i=1}^{\frac{n}7lx9byv}\sum\limits_{i=1}^{\frac{m}6cfwe4w}i*j*d^2[gcd(i,j)=1]\) 注：\(i,j\)除了\(d\)，所以要乘回來，變成了\(d^2\)。 \(\sum\limits_{d=1}^{n}d\sum\limits_{i=1}^{\frac{n}9w5tkwu}\sum\limits_{i=1}^{\frac{m}x9eoe27}i*j\sum\limits_{k|gcd(i.j)}\mu(k)\) \(\sum\limits_{d=1}^{n}d\sum\limits_{k=1}^{\frac{n}1bdf2ht}\mu(k)k^2\sum\limits_{i=1}^{\frac{n}{dk}}i\sum\limits_{j=1}^{\frac{m}{dk}}j\) 然后設(shè)\(T=dk\) \(\sum\limits_{T=1}^{n}\sum\limits_{d|T}d\frac{T^2}{d^2}\mu(\frac{T}xc4rich)\sum\limits_{i=1}^{T}i\sum\limits_{j=1}^{T}j\) 設(shè)\(g(n)=\sum\limits_{i=1}^{n}i=\frac{n(n 1)}{2}\) \(\sum\limits_{T=1}^{n}T^2g(\frac{n}{T})g(\frac{m}{T})\sum\limits_{d|T}\frac{\mu(\frac{T}p92y9to)}u4kk2di\) 這個式子確確實實是對的，但是\(nlogn\)預(yù)處理太頂了。 所以我們需要觀察我們在那里漏了什么東西。 其實我們發(fā)現(xiàn)對于 \(\sum\limits_{d=1}^{n}d\sum\limits_{k=1}^{\frac{n}sh4tbmh}\mu(k)k^2\sum\limits_{i=1}^{\frac{n}{dk}}i\sum\limits_{j=1}^{\frac{m}{dk}}j\) 我們設(shè)\(sum(n,m)=\sum\limits_{d=1}^{n}\mu(d)d^2\sum\limits_{i=1}^{\frac{n}9sbualr}i\sum\limits_{j=1}^{\frac{m}ayazxkv}j\)。 這個式子，只要我們處理除了\(\mu\)，就可以數(shù)論分塊\(O(\sqrt{n})\)解決。 式子化為 \(\sum\limits_{d=1}^{n}d*sum(\frac{n}xlv99s9,\frac{m}tpikruo)\) 也是數(shù)論分塊。 那么就可以\(O(n)\)做出來啦！ 7這道題目也是一道套路題呀。 \(n<=m\) \(\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{m/d}[gcd(i,j)==1]φ(i)φ(j)\) \(\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{n/d}\sum\limits_{j=1}^{m/d}φ(i)φ(j)\sum\limits_{k|gcd(i,j)}\mu(k)\) \(\sum\limits_{d=1}^{n}\sum\limits_{k=1}^{n/d}\mu(k)\sum\limits_{k|i}^{n/d}φ(i)\sum\limits_{k|j}^{m/d}φ(j)\) \(\sum\limits_{d=1}^{n}\sum\limits_{k=1}^{n/d}\mu(k)\sum\limits_{i=1}^{n/dk}φ(ik)\sum\limits_{j=1}^{m/dk}φ(jk)\) 然后我們設(shè)\(g(n,k)\)表示的是\(\sum\limits_{i=1}^{n}φ(ik)\)。 那么這個是可以\(O(nlogn)\)的時間和空間預(yù)處理出來的。 \(\sum\limits_{d=1}^{n}\sum\limits_{k=1}^{n/d}\mu(k)g(n/dk,k)g(m/dk,k)\) 設(shè)\(T=dk\) \(\sum\limits_{T=1}^{n}\sum\limits_{k|T}\mu(k)g(n/T,k)g(m/T,k)\) 我們再設(shè)\(sum(x,y,T)=\sum\limits_{k|T}\mu(k)g(x,k)g(y,k)\)。 但是猛然發(fā)現(xiàn)這個玩意微積分完后的時間和空間復(fù)雜度是\(O(n^2)\)的，怎么用的起呀！?。?！ 但是這個時候有人靈光一閃，如果如果我們只處理\(x,y<=B\)的數(shù)字呢？（其實我們發(fā)現(xiàn)\(k>=\frac{n}{B}\)） 我們設(shè)\(B=\sqrt{n}\)。 那么就是\(O(n\sqrt{n})\)的空間了?。。?/p> 但是預(yù)處理怎么辦呢？ 我們就爆枚吧QMQ。 爆枚時間\(O(n\sqrt{n}logn)\)，可以證明一個數(shù)字的約數(shù)個數(shù)的期望是\(log\)的。 然后我們就可以對于\(k>=\frac{n}{B}\)可以數(shù)論分塊，而對于\(k<=\frac{n}{B}\)爆枚！??！ 時間復(fù)雜度\(O((T n)\sqrt{n}logn)\) 當然，這道題目很神奇，\(B\)取小一點反而能AC，估計又是常數(shù)問題。 8這道題目其實是道SB題，只不過因為很多人（包括我）都是第一次遇到\(\prod\)！?。。ㄖv真我一開始打算用\(log\)換成加法，但是發(fā)現(xiàn)小數(shù)次冪我解決不了。。。） \(\prod\limits_{d=1}^{n}f(d)^{\sum\limits_{i=1}^{n/d}\sum\limits_{i=1}^{m/d}[gcd(i,j)==1]}\) \(\prod\limits_{d=1}^{n}f(d)^{\sum\limits_{i=1}^{n/d}\sum\limits_{i=1}^{m/d}\sum\limits_{k|gcd(i,j)}\mu(k)}\) \(\prod\limits_{d=1}^{n}f(d)^{\sum\limits_{k=1}^{n/d}\mu(k)\sum\limits_{i=1}^{n/dk}\sum\limits_{i=1}^{m/dk}}\) 要不是多組數(shù)據(jù)我就用第6題方法艸過去了 設(shè)\(T=dk\)（我就不會下一步怎么化然后看了題解） \(\prod_{T=1}^{n}\prod_{d|T}f(d)^{\mu(\frac{T}iylcmlx)(n/T)(m/T)}\) 后面那個\((n/T)(m/T)\)用快速冪加數(shù)論分塊爆搞。 但是我們要先處理出\(\prod_{d|T}f(d)^{\mu(\frac{T}5qhiaxj)}\)的前綴積。。。 所以我們\(O(nlogn)\)預(yù)處理一下，然后就可以做了。 時間復(fù)雜度：\(O(n\log{mod} nlogn T\sqrt{n}\log{mod})\) 實際上而言。\((n/T)(m/T)\)可以\(\%(mod-1)\)（費馬小定理） 9還有?。?！ 腎都炸了?。。?！ 博主你是不是故意的！??！ 最后一道題目放一個毒瘤之神？ 毒瘤之神： 方法1： \(φ(i,j)=φ(\frac{i}{gcd(i,j)})*φ(j*gcd(i,j))\) 但是明眼人一看就發(fā)現(xiàn)錯了。 \(\frac{i}{gcd(i,j)}\)不一定與\(gcd(i,j)\)互質(zhì)。 方法2： \(φ(ij)=\frac{φ(i)φ(j)gcd(i,j)}{φ(gcd(i,j))}\) \(\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{n}\sum\limits_{i=1}^{m}φ(i)*φ(j)\fracop7auqi{φ(d)}[gcd(i,j)==d]\) \(\sum\limits_{d=1}^{n}\sum\limits_{i=1}^{n/d}\sum\limits_{i=1}^{m/d}\sum\limits_{k|gcd(i,j)}\fraccgd9bmr{φ(d)}\mu(k)φ(id)*φ(jd)\) \(\sum\limits_{d=1}^{n}\sum\limits_{k=1}^{n/d}\sum\limits_{i=1}^{n/dk}\sum\limits_{i=1}^{m/dk}\mu(k)φ(ikd)*φ(jkd)\fracpcxqybl{φ(d)}\) \(\sum\limits_{T=1}^{n}\sum\limits_{k|T}\sum\limits_{i=1}^{n/T}\sum\limits_{i=1}^{m/T}\mu(k)φ(iT)φ(jT)\frac{\frac{T}{k}}{φ(\frac{T}{k})}\) \(\sum\limits_{T=1}^{n}\sum\limits_{k|T}\mu(k)\frac{\frac{T}{k}}{φ(\frac{T}{k})}\sum\limits_{i=1}^{n/T}φ(iT)\sum\limits_{i=1}^{m/T}φ(jT)\) \(G(n,k)=\sum\limits_{i=1}^{n}φ(ik)\) \(F(T)=\sum\limits_{k|T}\mu(k)\frac{\frac{T}{k}}{φ(\frac{T}{k})}\) \(S(x,y,z)=\sum\limits_{T=1}^{x}\sum\limits_{k|T}\mu(k)\frac{\frac{T}{k}}{φ(\frac{T}{k})}\sum\limits_{i=1}^{y}φ(iT)\sum\limits_{i=1}^{z}φ(jT)\) \(S(x,y,z)=S(x-1,y,z) F(x)G(y,x)G(z,x)\) 所以我們只要處理\(x<=n,1<=y,z<=B\)的，對于\(y,z>B\)的我們暴力處理，所以時間復(fù)雜度是\(O(T(B \frac{n}{B}) nB^2)\)，而且空間復(fù)雜度是\(O(nB^2)\)。 當\(B=35\)時這個算法跑的很快。 小結(jié)&總結(jié)證明
|
|
|
