[数论] 一个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

下载 (10.42 KB)

2020-1-26 11:43

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

下载 (5.52 KB)

2020-1-26 20:47

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

复制代码