import sys def main(): import sys input = sys.stdin.read data = input().split() idx = 0 T = int(data[idx]) idx += 1 N = 220009 b = [False] * (N + 10) p = [0] * 6000000 # 筛出sqrt(n)内的素数 def getp(): cnt = 0 for i in range(2, N + 1): if not b[i]: cnt += 1 p[cnt] = i j = 1 while j <= cnt and i * p[j] <= N: b[i * p[j]] = True if i % p[j] == 0: break j += 1 p[0] = cnt getp() mod = 10**9 + 7 Test = [2, 3, 5, 7, 11, 13, 17, 19] def Mul(x, y, z): return (x * y - ((x / z) * y) * z + z) % z def powmod(x, y, z): if y == 0: return 1 if y & 1: return (x * powmod(x, y ^ 1, z)) % z t = powmod(x, y >> 1, z) return (t * t) % z def mr(x, y): if x == 1: return False if x == y: return True t = x - 1 u = 0 while t % 2 == 0: t //= 2 u += 1 now = powmod(y, t, x) while u > 0: u -= 1 nxt = (now * now) % x if nxt == 1 and now != 1 and now != x - 1: return False now = nxt return now == 1 def ispr(x): for i in range(8): if not mr(x, Test[i]): return False return True for _ in range(T): k = int(data[idx]) p1 = int(data[idx + 1]) q = int(data[idx + 2]) idx += 3 cnt = 0 i = 1 while i <= p[0] and k >= p[i]: if k % p[i] == 0: cnt += 1 while k % p[i] == 0: k //= p[i] i += 1 if k > 1: if ispr(k): cnt += 1 else: qwq = 0 for i in range(30, -1, -1): if (qwq + (1 << i)) * (qwq + (1 << i)) <= k: qwq += (1 << i) if qwq * qwq == k: cnt += 1 else: cnt += 2 print((pow(2, cnt, mod) * (q - p1 + 1)) % mod) if __name__ == '__main__': main()

题库

题库

377.「GMOI R1-T3」Number Pair

提交记录

测试用例