网格剪纸

有一张$w\times h$大小的矩形网格纸，$w>h$均为整数，网格是边长为1的小正方形。

若沿着网格线将这张纸剪成两片，再将其不重叠地重新组合到一起就可能得到不同边长的新矩形。

例如，用一张$9\times 4$的矩形网格纸，可以通过剪裁和重排得到$18\times 2$、$12\times 3$和$6\times 6$这几种矩形，如下所示：

类似地，用$9\times 8$的矩形网格纸可以得到$18\times 4$和$12\times 6$的矩形。

记$F(w,h)$为用$w\times h$的矩形网格纸可得的新的满足$w>h$的矩形的数量。

可以验证，$F(2,1)=0, F(2,2)=1, F(9,4)=3, F(9,8)=2$。再令 $$G(N)=\sum_{0 < h\le w\le N}F(w,h),$$ 则有$G(10)=55, G(10^3)=971745, G(10^5)=9992617687$。

求$G(10^{12}) \bmod 10^8$。

本题难度:

解答

本题的命题者提供了以下公式

其中涉及的除法均为整除（取商的整数部分），$N=10^{12}$。

由于除法均为整除，因此一维求和事实上是对一分段常值的函数求和，二维求和中先固定一个变量后也可以转换为同样的问题，最终结果是$15614292$。

注：以下代码改编自官网论坛。因需使用math.isqrt函数，代码为Python 3。

import math

n=10**12
m=10**8
bound=10**6

def f(n,d):
    b=math.isqrt(n//d)
    s=sum(n//d//k for k in range(d+1,b+1)) if d < b else n//d//(d+1)
    d2=max(b,d+1)
    p=d2
    for k in range(n//d//d2,0,-1):
        x=n//d//k
        s+=(x-p)*k
        p=x
    return 2*s+n//d//d

print((sum((n//d-1)*(n//(d+1)) for d in range(1,bound+1))+sum(((n//d-n//(d+1))*(d-1)*d-d+1) for d in range(1,bound))-sum(f(n,d) for d in range(2,bound+1)))%m)