一个wifi密码和计数问题

hbghlyj

\[\mathop \sum \limits_{i = 1}^n \mathop \sum \limits_{j = i + 1}^n \left[ {i + j|ij} \right],n=998244353\]
里面是命题的布尔值，能整除取1，不能整除取0
也就是1到n的正整数能组成多少对(i,j)使得i<j,$i+j|ij$
设ij=m(i+j),$\frac1m=\frac1i+\frac1j\in\left[\frac2n,2\right],m\in\left[ {1,\left\lfloor {\frac{n}{2}} \right\rfloor } \right]$,$(i-m)(j-m)=m^2$,

hbghlyj

直接暴力计算会溢出，但我们可以找到n=99的答案，作为检验
按1#的算法

tommywong

未解決,但係先提供一個方向

$(i,j)=d,~i=ad,~j=bd,~(a,b)=1$

$k(a+b)=abd\Rightarrow
a|bk,~b|ak\Rightarrow
a|k,~b|k\Rightarrow
ab|k$

$(a+b)c=d$

$i=ac(a+b),~j=bc(a+b)\le n,~(a,b)=1$

所求嘅數應該等於$
\displaystyle\sum_{1\le a<b\le n\atop
(a,b)=1}\left[\frac{n}{b(a+b)}\right]$

tommywong

答案應該係3972243386

為咗減少算法時間，我再出多兩個條件收窄a,b範圍

$n\ge b(a+b)>2a^2\Rightarrow a<\sqrt{\dfrac{n}{2}}$

$b^2+ab<n\Rightarrow b=\dfrac{-a+\sqrt{a^2+4b}}{2}$

然後再喺進入b循環之前篩走非互質嘅數

結果4分鐘內搞掂

Elapsed time is 238.309805 seconds.

1. clc;clear;
2. n=998244353;
3. s=0;
4. tic
5. for a=1:sqrt(n/2)
6.     b0=a+1:(-a+sqrt(a^2+4*n))/2;
7.     b0=setdiff(unique((gcd(b0,a)==1).*b0),0);
8.     nb=length(b0);
9.     for l=1:nb
10.         s=s+fix(n/b0(l)/(a+b0(l)));
11.     end
12. end
13. toc

Copy the Code