0372 射线束
* * * *
拉格朗日计划
* * * *
射线束

记$R(M,N)$为满足$M < x,y\le N$且$\lfloor y^2/x^2\rfloor$为奇数的整数对$(x,y)$的总数。

可以验证$R(0,100)=3019$以及$R(100,10000)=29750422$。

求$R(2\times 10^6, 10^9)$。

本题难度:



解答

本题与第325题的解法相似,以下代码改编自官方论坛,效率稍高一些,最终结果是$301450082318807027$。\\ 注:因用到math.isqrt等函数,以下代码为Python 3。

from math import floor,sqrt,isqrt
from decimal import *
getcontext().prec = 20

def g(x,y):
    if x <= 0 or y <= 0:
        return 0
    if x <= 1:
        return g(x+1,y)-y*(y+1)//2
    if x < 2:
        return int(x*y)*(1+int(x*y))//2-g(x/(x-1),int((x-1)*y))
    return g(x-int(x),y)+int(x)*y*(y+1)//2

m=2000000
n=10**9

r=0
k=1
a=floor(n/sqrt(k))

while a>m:
    b=floor(n/sqrt(k+1))
    u,v=Decimal(k).sqrt(),Decimal(k+1).sqrt()
    r+=g(v,max(m,b))-g(v,m)+g(u,m)-g(u,a)+(a-max(m,b))*n
    if isqrt(k+1)**2==k+1:   
        r+=int(m*sqrt(k+1))//isqrt(k+1)-n//isqrt(k+1)
    if isqrt(k)**2==k:
        r+=n//isqrt(k)-int(m*sqrt(k))//isqrt(k)
    k+=2
    a=floor(n/sqrt(k))

print(r)