解題報(bào)告自選題eulerian

1、EX1【題意簡(jiǎn)述】求所有滿足 ab=N 的有序數(shù)對(duì)(a,b)的最大公約數(shù)的和?！舅惴ǚ治觥堪褑?wèn)題要求的寫(xiě)成表達(dá)式的形式：NN i1 ji1( i, j)考慮枚舉了(i,j)之后，原表達(dá)式可以化簡(jiǎn)為：Nk * |(i, j) |k 1( i, j) 1, i * k N, j * k N |假設(shè)枚舉了其中較大的 i，那么，j 需要滿足的條件是(i,j)=k 和 ji，變形一下 i/k與 j/k 互質(zhì)，ji。用語(yǔ)言表述就是要求比 i/k 小的與 i/k 互質(zhì)的數(shù)的個(gè)數(shù)。即(i / k) 。再進(jìn)一步化簡(jiǎn)表達(dá)式：i*k NNk * (i)k 1i1這里，(i) 是函數(shù)2，表示與 i 互質(zhì)的數(shù)的個(gè)數(shù)。有

2、了以上推導(dǎo)，不難設(shè)計(jì)出一個(gè) N*sqrt(N)*Q 的算法：算法 1：先預(yù)處理函數(shù)，之后枚舉數(shù)對(duì)中較大的 i 和它們的統(tǒng)計(jì)滿足條件的j 的個(gè)數(shù)。值 k， 之后再用函數(shù)來(lái)時(shí)間復(fù)雜度:O(N*sqrt(N)*Q)空間復(fù)雜度:O(N)12本題是 spoj3871 的函數(shù)參見(jiàn)EXs totient function由于 N 的規(guī)模并不是很大，因此，考慮通過(guò)預(yù)處理去掉時(shí)間復(fù)雜度中的 Q。設(shè) f(n)為要求計(jì)算的的和，考慮 f(n+1)與 f(n)的關(guān)系:f(n+1)-f(n)=(n+1，1)+(n+1，2)不難發(fā)現(xiàn)，這里所有的值都是 n+1 的約數(shù)，同時(shí)，數(shù)對(duì)中較大的那個(gè)數(shù) n+1 已經(jīng)確定，因此，它們

3、的差值是可以用 sqrt(n)的時(shí)間計(jì)算出來(lái)的。這樣就可以通過(guò)預(yù)處理的方式計(jì)算出所有 n 的。算法 2：先預(yù)處理函數(shù)，之后采用類似算法 2 的做法求出 f(n+1)-f(n)，由此求出所有的 f(n)。對(duì)于所有的詢問(wèn)，直接查表回答。時(shí)間復(fù)雜度:O(N*sqrt(N)+Q)空間復(fù)雜度:O(N)至此，已經(jīng)設(shè)計(jì)出了復(fù)雜度相當(dāng)優(yōu)秀的算法，但是，N*sqrt(N)的時(shí)間復(fù)雜度還是以通過(guò)本題，還需要一個(gè)小小的技巧將復(fù)雜度降至N*log(N)。來(lái)分析一下算法的瓶頸，在枚舉(i,j)的時(shí)候，進(jìn)行了很多無(wú)用的枚舉，因?yàn)?i,j)必須是 i 的約數(shù)，而要枚舉 i 的約數(shù)時(shí)，必須花費(fèi) sqrt(i)的時(shí)間來(lái)枚舉，其

4、中又有很多不是 i的約數(shù)，但是也被枚舉了。有沒(méi)辦法，讓每次枚舉出來(lái)的數(shù)都是 i 的約數(shù)呢?可以先枚舉(i,j)，再枚舉 i，因?yàn)?i 必須是(i,j)這里就有一個(gè)實(shí)現(xiàn)的小技巧，的倍數(shù)，所以每一個(gè)枚舉出來(lái)的 i 都是滿足條件的，這樣就減少了冗余的枚舉。來(lái)計(jì)算一下時(shí)間復(fù)雜度：O(N/1+N/2+N/3+N/N)=O(N *log(N)算法 3：先預(yù)處理函數(shù)，之后采用類似篩選法的方法來(lái)實(shí)現(xiàn)算法 3，求出 f(n-1)-f(n)。時(shí)間復(fù)雜度:O(N*log(N)+Q)空間復(fù)雜度:O(N)LCM SUM3【題意簡(jiǎn)述】給出N，計(jì)算 LCM(1,n) + LCM(2,n) + . + LCM(n,n)的和，

5、LCM(i,n)表示 i 和n 的最小公倍數(shù)?！舅惴ǚ治觥繃L試把 lcm 也化歸到函數(shù)上，做一個(gè)簡(jiǎn)單的變形：lcm(x,N)=x*N/(x,N)枚舉意，(x,N)之后，那么，問(wèn)題就是要求與 N/(x,N)互質(zhì)的所有 x/(x,N)的和。注函數(shù)求的是與某個(gè)數(shù)互質(zhì)的數(shù)的個(gè)數(shù)，那么，怎么求和呢？這里，有一個(gè)簡(jiǎn)單而往往被大家忽視的性質(zhì)：性質(zhì) 1：對(duì)于任何一個(gè)數(shù)N，如果 i 與 N 互質(zhì)，那么 N-i 也與 N 互質(zhì)。證明：假設(shè)(N,i)=1,(N,N-i)=k(k1)k|N，k|N-ik|i與假設(shè)，假設(shè)不成立。有了這一性質(zhì)，問(wèn)題就徹底轉(zhuǎn)化成了求函數(shù)。根據(jù)性質(zhì) 1，可以把所有與N 互質(zhì)的數(shù)兩兩分組，每一組的和為 N，因此，設(shè)與 N互質(zhì)的數(shù)的和為 f(N),則 f(N)=phi(N)*N/2。至此，結(jié)合上一題的想法，可以得到了解決本題的算法：算法 1：先預(yù)處理出函數(shù)，然后再求出所有的 f(N)，再根據(jù)以上