1≤y ≤x :有phi(x )个,这是欧拉函数的定义.

x +1≤y≤2x :也有phi(x )个,因为gcd(x +i ,x )=gcd(x ,i ).2x +1≤y ≤3x :也有phi(x )个,因为gcd(2x +i ,x )=gcd(x ,i ).......

kx +1≤y ≤b:直接统计,需要O (x )时间.

换句话说,每次需要计算phi(x )和进行O (x )次直接判断,计算phi(x )需要O (x1/2 )时间,而直接判断只需要O (1)时间.再加上枚举x 的所有a 种可能,总时间为O (a2 ).例题10-28 (问题抽象)高速公路(Highway, ACM/ICPC CERC 2006,