數論神題——進擊的羊角獸

數論神題

進擊的羊角獸

題目描述：

求滿足 \(a+b|ab(a,b \leq n,a \neq b)\)的有序數對\((a,b)\)的個數。

solution

設\((a,b)=d , (a < b \leq n)\),則$ a=xd , b=yd , ( x < y )$

\(a+b|ab\)

\(=(x+y)d|xyd^2\)

\(\because (x+y, x)=1,(x+y, y)=1\)

\(\therefore (x+y)|d\)

$\therefore x < y \leq \sqrt{n} $

設\(d=z(x+y)\),則\(a=xz(x+y) , b=yz(x+y)\)

即原問題為求數對\((x, y, z)( x < y \leq \sqrt{n}, z \leq \lfloor \frac {n}{y(x+y)} \rfloor)\)

\[Ans=\sum_{x < y} \sum_{(x, y)=1} \lfloor \frac {n}{y(x+y)} \rfloor\]

\[=\sum_{x < y} \sum_{d=(x, y)}\varepsilon(d) \lfloor \frac {n}{y(x+y)} \rfloor\]

\[=\sum_{x < y} \sum_{d|(x,y)} \mu(d) \lfloor \frac {n}{y(x+y)} \rfloor\]

\[=\sum_{x < y,d|x,d|y} \mu(d) \lfloor \frac {n}{y(x+y)} \rfloor\]

設\(x=x'd, y=y'd\)

\[=\sum_{x' < y'} \mu(d) \lfloor \frac {n}{y'(x'+y')d^2} \rfloor\]

為了方便，下面的\(x',y' \text 用回 x,y \text 表示\)

\[=\sum_{x < y} \mu(d) \lfloor \frac {n}{y(x+y)d^2} \rfloor (d \leq \sqrt{n})\]

現在就來解釋一下上面的\(\varepsilon(), \mu()\)

這個是莫比烏斯函數的性質。

這樣只有當\((x,y)=1\)時，\(\lfloor \frac {n}{y(x+y)} \rfloor\) 才會被算進去。

\(\mu(n)\)很容易就可以算出來，顯然當\(n=1\)時\(\mu(1)=1\)，對于一個數\(n\)，它的所有約數的\(\mu()\)的和為\(0\)，而\(n\)的其中一個約數就是\(n\)，小于\(n\)的\(\mu()\)又已經算出來了，就可以把\(\mu(n)\)算出來。

\[\sum_{x < y} \mu(d) \lfloor \frac {n}{y(x+y)d^2} \rfloor (d \leq \sqrt{n})\]

設

\[f(t)=\sum_{x < y} \lfloor \frac {t}{y(x+y)} \rfloor\]

則

\[Ans=\sum_{x < y} \mu(d)f(\frac {n}{d^2})\]

\[f(t)=\sum_{x < y} \lfloor \frac {t}{y(x+y)} \rfloor\]

\[=\sum_{x < y, z \leq \lfloor \frac {t}{y(x+y)} \rfloor} 1\]

\[=\sum_{x \leq y-1, y(x+y) \leq \lfloor \frac {t}{z} \rfloor} 1\]

\[=\sum_{x \leq y-1, x \leq \lfloor \frac {t}{zy} \rfloor -y} 1\]

\[f(t)=\sum h(\lfloor \frac {t}{z} \rfloor)\]

終于都推完了。

答案記得乘2

分析一下時間復雜度。

\(h(s)\)：因為最小值要比大于\(0\)，所以\(y \leq \sqrt {s}\),而\(s=\lfloor \frac {t}{z} \rfloor=\lfloor \frac {n}{zd^2} \rfloor\)，所以\(s\)最多有\(2\sqrt {n}\)個，時間復雜度為：

\[\int_{0}^{\sqrt {n}} (\sqrt {x} + \sqrt { \frac {n}{x}} ) \mathrm{d}x\]

\(f(s)\):分析同上，一個\(f(s)\)需要\(\sqrt {s}\)的時間

\(Ans\):枚舉\(d\)要\(\sqrt {n}\)，算\(f(s)\)需要\(\sqrt {s}\)的時間，總的時間復雜度為：

\[\int_{0}^{\sqrt {n}} (\sqrt {x} + \sqrt { \frac {n}{x}} ) \mathrm{d}x\]

預處理\(h(s)\)，所以整個算法的時間為：

\[\int_{0}^{\sqrt {n}} (\sqrt {x} + \sqrt { \frac {n}{x}} ) \mathrm{d}x\]

\[=\frac {8}{3} n^{ \frac {3}{4}}\]

貼代碼：

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <map>
#include <deque>
#include <queue>
using namespace std;typedef long long LL;
const int maxn=int(1e6)+100;LL n, ans;
int qn;
LL u[maxn], h[maxn], hv[maxn];void getu()
{for (int i=1; i<=qn; ++i) u[i]=1;for (int i=2; i<=qn; ++i){u[i]=-u[i];for (int j=2; i*j<=qn; ++j) u[i*j]+=u[i];}
}
LL geth1(LL num)
{int cut=(sqrt(1+8*num)+1)*0.25;int fi=(int)floor(sqrt(num));LL ret=LL(cut-1)*cut/2-(LL)(cut+1+fi)*(fi-cut)/2;for (int i=cut+1; i<=fi; ++i)ret+=num/i;return ret;
}
void geth()
{for (int i=1; i<=qn; ++i){h[i]=geth1(i);hv[i]=geth1(n/i);           }
}
LL getf(LL num)
{LL f=0;int fi=(int)floor(sqrt(num));for (int i=1; i<=fi; ++i)f+=h[i]*(num/i-num/(i+1));for (int i=1; i<=fi; ++i){if (num / i <= fi) continue;if (num/i>sqrt(n)) f+=hv[n/(num/i)];else f+=h[num/i];}/*if (LL(sqrt(num))*LL(sqrt(num))==num)f-=h[LL(sqrt(num))];*/return f;
}
void solve()
{getu();geth();for (int i=1; i<=qn; ++i)ans+=u[i]*getf(n/((long long)i*i));
}
int main()
{freopen("nixgnoygnay.in", "r", stdin);freopen("nixgnoygnay.out", "w", stdout);scanf("%I64d", &n);qn=(int)floor(sqrt(n));solve();printf("%I64d\n", ans*2);return 0;
}