等差数列数
Number of arithmetic progressions
给定 N 个从 1 到 N 的连续整数。
计算有多少种方法可以选择多个数字（至少1个数字）使得它们形成等差级数（AP）modulo 1e9+7
定义L[N]就是答案
以2开头，以N结尾的AP数量=以1开头，以N-1结尾的AP数量
以1开头，以N结尾的AP个数为N-1的约数(=\tau(N-1))
所以，L[N] = L[N-1] + \tau(N-1)
但是 N <= 10^10 。算法必须是O(n)，我怎么计算\tau(n)?
您需要tau（或sigma0）功能（look here）。
要找到它，请将参数值分解为素数。值可能表示为
N = p1^q1 * p2^q2 * p3^q3 ... where p[i] are primes 2,3,5,7... and q[i] are corresponding powers
然后
tau(n) = (q1+1) * (q2+1) * (q3+1)....
例如，
60 = 2^2*3*5
tau(60)=3*2*2= 12 divisors (1,2,3,4,5,6,10,12,15,20,30,60)
分解为素数（在 O(sqrt(n)) 时间内）可能实现起来非常简单 - 尽可能除以 2，然后除以 3 和更大的奇数直到 sqrt(n)，计算幂。
给定 N 个从 1 到 N 的连续整数。
计算有多少种方法可以选择多个数字（至少1个数字）使得它们形成等差级数（AP）modulo 1e9+7
定义L[N]就是答案
以2开头，以N结尾的AP数量=以1开头，以N-1结尾的AP数量
以1开头，以N结尾的AP个数为N-1的约数(=\tau(N-1))
所以，L[N] = L[N-1] + \tau(N-1)
但是 N <= 10^10 。算法必须是O(n)，我怎么计算\tau(n)?
您需要tau（或sigma0）功能（look here）。
要找到它，请将参数值分解为素数。值可能表示为
N = p1^q1 * p2^q2 * p3^q3 ... where p[i] are primes 2,3,5,7... and q[i] are corresponding powers
然后
tau(n) = (q1+1) * (q2+1) * (q3+1)....
例如，
60 = 2^2*3*5
tau(60)=3*2*2= 12 divisors (1,2,3,4,5,6,10,12,15,20,30,60)
分解为素数（在 O(sqrt(n)) 时间内）可能实现起来非常简单 - 尽可能除以 2，然后除以 3 和更大的奇数直到 sqrt(n)，计算幂。