import macros macro Please(x): untyped = nnkStmtList.newTree() Please use Nim-ACL Please use Nim-ACL Please use Nim-ACL #[ include daylight/base ]# when not declared DAYLIGHT_BASE_HPP: const DAYLIGHT_BASE_HPP* = 1 import system import macros import algorithm import tables import sets import lists import intsets import critbits import sequtils import strutils import std/math import strformat import sugar let readToken* = iterator(oneChar: bool = false): string {.closure.}= while true: var line = stdin.readLine.split for s in line: if oneChar: for i in 0.. b: a = b return true return false proc chmax*[T](a: var T, b: T): bool {.discardable.} = if a < b: a = b return true return false const INF* = (1e9+100).int const LINF* = (4e18 + 100).int discard #[ import atcoder/math as atcodermath ]# when not declared ATCODER_MATH_HPP: const ATCODER_MATH_HPP* = 1 #[ import atcoder/internal_math ]# when not declared ATCODER_INTERNAL_MATH_HPP: const ATCODER_INTERNAL_MATH_HPP* = 1 import std/math type Barrett* = object m*, im*:uint proc initBarrett*(m:uint):auto = Barrett(m:m, im:cast[uint](-1) div m + 1) proc umod*(self: Barrett):uint = self.m {.emit: """ inline unsigned long long calc_mul(const unsigned long long &a, const unsigned long long &b){ return (unsigned long long)(((unsigned __int128)(a)*b) >> 64); } """.} proc calc_mul*(a,b:culonglong):culonglong {.importcpp: "calc_mul(#,#)", nodecl, inline.} proc quo*(self: Barrett, n:int | uint):int = let n = n.uint let x = calc_mul(n.culonglong, self.im.culonglong).uint let r = n - x * self.m return int(if self.m <= r: x - 1 else: x) proc rem*(self: Barrett, n:int | uint):int = let n = n.uint let x = calc_mul(n.culonglong, self.im.culonglong).uint let r = n - x * self.m return int(if self.m <= r: r + self.m else: r) proc quorem*(self: Barrett, n:int | uint):(int, int) = let n = n.uint let x = calc_mul(n.culonglong, self.im.culonglong).uint let r = n - x * self.m return if self.m <= r: (int(x - 1), int(r + self.m)) else: (int(x), int(r)) proc pow*(self: Barrett, n:uint | int, p:int):int = var a = self.rem(n) r:uint = if self.m == 1: 0 else: 1 p = p while p > 0: if (p and 1) != 0: r = self.mul(r, a.uint) a = self.mul(a.uint, a.uint).int p = p shr 1 return int(r) proc mul*(self: Barrett, a:uint, b:uint):uint {.inline.} = let z = a * b return self.rem(z).uint proc pow_mod_constexpr*(x, n, m:int):int = if m == 1: return 0 var r = 1 y = floorMod(x, m) n = n while n != 0: if (n and 1) != 0: r = (r * y) mod m y = (y * y) mod m n = n shr 1 return r.int proc is_prime_constexpr*(n:int):bool = if n <= 1: return false if n == 2 or n == 7 or n == 61: return true if n mod 2 == 0: return false var d = n - 1 while d mod 2 == 0: d = d div 2 for a in [2, 7, 61]: var t = d y = pow_mod_constexpr(a, t, n) while t != n - 1 and y != 1 and y != n - 1: y = y * y mod n t = t shl 1 if y != n - 1 and t mod 2 == 0: return false return true proc is_prime*[n:static[int]]():bool = is_prime_constexpr(n) proc inv_gcd*(a, b:int):(int,int) = var a = floorMod(a, b) if a == 0: return (b, 0) var s = b t = a m0 = 0 m1 = 1 while t != 0: var u = s div t s -= t * u; m0 -= m1 * u; # |m1 * u| <= |m1| * s <= b var tmp = s s = t;t = tmp; tmp = m0;m0 = m1;m1 = tmp; if m0 < 0: m0 += b div s return (s, m0) proc primitive_root_constexpr*(m:int):int = if m == 2: return 1 if m == 167772161: return 3 if m == 469762049: return 3 if m == 754974721: return 11 if m == 998244353: return 3 var divs:array[20, int] divs[0] = 2 var cnt = 1 var x = (m - 1) div 2 while x mod 2 == 0: x = x div 2 var i = 3 while i * i <= x: if x mod i == 0: divs[cnt] = i cnt.inc while x mod i == 0: x = x div i i += 2 if x > 1: divs[cnt] = x cnt.inc var g = 2 while true: var ok = true for i in 0..= m: result += n * (n - 1) div 2 * (a div m) a = a mod m if b >= m: result += n * (b div m) b = b mod m let y_max = a * n + b if y_max < m: break n = y_max div m b = y_max mod m swap(m, a) discard import std/math as math_lib_of_math proc pow_mod*(x,n,m:int):int = assert 0 <= n and 1 <= m if m == 1: return 0 let bt = initBarrett(m.uint) var r = 1.uint y = x.floorMod(m).uint n = n while n != 0: if (n and 1) != 0: r = bt.mul(r, y) y = bt.mul(y, y) n = n shr 1 return r.int proc inv_mod*(x, m:int):int = assert 1 <= m let z = inv_gcd(x, m) assert z[0] == 1 return z[1] proc crt*(r, m:openArray[int]):(int,int) = assert r.len == m.len let n = r.len var (r0, m0) = (0, 1) for i in 0.. lcm(m0, m1) if r0 < 0: r0 += m0 return (r0, m0) proc floor_sum*(n, m, a, b:int):int = assert n in 0..<(1 shl 32) assert m in 1..<(1 shl 32) var (a, b) = (a, b) var ans = 0.uint if a < 0: var a2:uint = floorMod(a, m).uint ans -= n.uint * (n - 1).uint div 2 * ((a2 - a.uint) div m.uint) a = a2.int if b < 0: var b2:uint = floorMod(b, m).uint ans -= n.uint * ((b2 - b.uint) div m.uint) b = b2.int return cast[int](ans + floor_sum_unsigned(n.uint, m.uint, a.uint, b.uint)) discard proc solve() = var T = read(int) for _ in 0.. A: echo 0 continue if K == A: echo (M div A) - 1 - ((M div B) - 1) + ((M div lcm(A, B)) - 1) continue var (Y, Z) = crt(@[0, K], @[A, B]) var ans = M div Z if M mod Z >= Y: ans += 1 (Y, Z) = crt(@[0, K], @[B, A]) ans += M div Z if M mod Z >= Y: ans += 1 echo ans solve()