結果
問題 | No.2280 FizzBuzz Difference |
ユーザー |
|
提出日時 | 2023-04-21 22:25:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 162 ms / 2,000 ms |
コード長 | 5,285 bytes |
コンパイル時間 | 379 ms |
コンパイル使用メモリ | 82,488 KB |
実行使用メモリ | 80,204 KB |
最終ジャッジ日時 | 2024-11-06 15:56:33 |
合計ジャッジ時間 | 2,207 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 7 |
ソースコード
import sys,random,bisectfrom collections import deque,defaultdictfrom heapq import heapify,heappop,heappushfrom itertools import permutationsfrom math import gcd,logfrom math import sqrt, ceilfrom bisect import bisect_left, bisect_rightfrom typing import Iterableinput = lambda :sys.stdin.readline().rstrip()mi = lambda :map(int,input().split())li = lambda :list(mi())class SegmentTree:def __init__(self, init_val, segfunc, ide_ele):n = len(init_val)self.segfunc = segfuncself.ide_ele = ide_eleself.num = 1 << (n - 1).bit_length()self.tree = [ide_ele] * 2 * self.numself.size = nfor i in range(n):self.tree[self.num + i] = init_val[i]for i in range(self.num - 1, 0, -1):self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])def update(self, k, x):k += self.numself.tree[k] = xwhile k > 1:k >>= 1self.tree[k] = self.segfunc(self.tree[2*k], self.tree[2*k+1])def query(self, l, r):if r==self.size:r = self.numres = self.ide_elel += self.numr += self.numright = []while l < r:if l & 1:res = self.segfunc(res, self.tree[l])l += 1if r & 1:right.append(self.tree[r-1])l >>= 1r >>= 1for e in right[::-1]:res = self.segfunc(res,e)return resdef _inv_gcd(a,b):a %= bif a == 0:return (b, 0)# Contracts:# [1] s - m0 * a = 0 (mod b)# [2] t - m1 * a = 0 (mod b)# [3] s * |m1| + t * |m0| <= bs = bt = am0 = 0m1 = 1while t:u = s // ts -= t * um0 -= m1 * u # |m1 * u| <= |m1| * s <= b# [3]:# (s - t * u) * |m1| + t * |m0 - m1 * u|# <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u)# = s * |m1| + t * |m0| <= bs, t = t, sm0, m1 = m1, m0# by [3]: |m0| <= b/g# by g != b: |m0| < b/gif m0 < 0:m0 += b // sreturn (s, m0)def crt(r,m):assert len(r) == len(m)n = len(r)# Contracts: 0 <= r0 < m0r0 = 0m0 = 1for i in range(n):assert 1 <= m[i]r1 = r[i] % m[i]m1 = m[i]if m0 < m1:r0, r1 = r1, r0m0, m1 = m1, m0if m0 % m1 == 0:if r0 % m1 != r1:return (0, 0)continue# assume: m0 > m1, lcm(m0, m1) >= 2 * max(m0, m1)'''(r0, m0), (r1, m1) -> (r2, m2 = lcm(m0, m1));r2 % m0 = r0r2 % m1 = r1-> (r0 + x*m0) % m1 = r1-> x*u0*g % (u1*g) = (r1 - r0) (u0*g = m0, u1*g = m1)-> x = (r1 - r0) / g * inv(u0) (mod u1)'''# im = inv(u0) (mod u1) (0 <= im < u1)g, im = _inv_gcd(m0, m1)u1 = m1 // g# |r1 - r0| < (m0 + m1) <= lcm(m0, m1)if (r1 - r0) % g:return (0, 0)# u1 * u1 <= m1 * m1 / g / g <= m0 * m1 / g = lcm(m0, m1)x = (r1 - r0) // g % u1 * im % u1'''|r0| + |m0 * x|< m0 + m0 * (u1 - 1)= m0 + m0 * m1 / g - m0= lcm(m0, m1)'''r0 += x * m0m0 *= u1 # -> lcm(m0, m1)if r0 < 0:r0 += m0return (r0, m0)def solve(M,A,B,K):g = gcd(A,B)M //= gif K % g:return 0K //= gA //= gB //= gif A < K:return 0res = 0if A == K:mini_n = 1maxi_n = M//Amini_b = (A*mini_n//B)maxi_b = (A*maxi_n//B)diff = maxi_b - mini_bx = (maxi_n-mini_n) - diffy = M//(A*B)return x + y"""By-Ax=Kのパターン"""r,_ = crt([0,K],[B,A])y0 = (r//B)x0 = ((r-K)//A)"""y = y0 + A*nx = x0 + B*n"""#print(x0,y0,M)if y0 <= M:min_n = 0max_n = min((M//B-y0)//(A),(M//A-x0)//(B))check_y = (B*y0)//A + y0 - (y0//A)check_x = x0 + (A*x0)//B - (x0//B)#print(check_x,check_y,max_n)if check_y == check_x + 1:res += max_n - min_n + 1"""Ay-Bx=Kのパターン"""r,_ = crt([0,K],[A,B])y0 = (r//A)x0 = ((r-K))//B"""y = y0 + B*nx = x0 + A*n"""if y0 <= M:min_n = 0max_n = min((M//A-y0)//(B),(M//B-x0)//(A))check_y = y0 + (A*y0)//B - (y0//B)check_x = (B*x0)//A + x0 - (x0//A)if check_y == check_x + 1:res += max_n - min_n + 1return resdef brute(M,A,B,K):X = [n for n in range(1,M+1) if n%A == 0 or n%B == 0]res = 0for i in range(len(X)-1):if X[i+1]-X[i] == K:res += 1return reswhile False:A = random.randint(2,20)B = random.randint(A+1,21)M = random.randint(5000,10000)K = random.randint(1,A-1)#M,A,B,K = 60,7,10,3print(M,A,B,K,solve(M,A,B,K),brute(M,A,B,K))assert solve(M,A,B,K) == brute(M,A,B,K)for _ in range(int(input())):M,A,B,K = mi()print(solve(M,A,B,K))