結果
問題 | No.826 連絡網 |
ユーザー | McGregorsh |
提出日時 | 2023-07-07 21:04:16 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 12,532 bytes |
コンパイル時間 | 317 ms |
コンパイル使用メモリ | 82,444 KB |
実行使用メモリ | 328,036 KB |
最終ジャッジ日時 | 2024-07-21 16:41:08 |
合計ジャッジ時間 | 6,667 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 161 ms
96,896 KB |
testcase_01 | AC | 164 ms
91,264 KB |
testcase_02 | AC | 172 ms
91,720 KB |
testcase_03 | AC | 180 ms
92,160 KB |
testcase_04 | AC | 181 ms
92,072 KB |
testcase_05 | AC | 182 ms
91,692 KB |
testcase_06 | AC | 182 ms
91,712 KB |
testcase_07 | AC | 187 ms
92,032 KB |
testcase_08 | AC | 178 ms
91,776 KB |
testcase_09 | AC | 182 ms
92,160 KB |
testcase_10 | AC | 178 ms
92,160 KB |
testcase_11 | AC | 181 ms
91,708 KB |
testcase_12 | TLE | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
ソースコード
import mathfrom bisect import bisect_left, bisect_right, insortfrom typing import Generic, Iterable, Iterator, TypeVar, Union, ListT = TypeVar('T')class SortedMultiset(Generic[T]):BUCKET_RATIO = 50REBUILD_RATIO = 170def _build(self, a=None) -> None:"Evenly divide `a` into buckets."if a is None: a = list(self)size = self.size = len(a)bucket_size = int(math.ceil(math.sqrt(size / self.BUCKET_RATIO)))self.a = [a[size * i // bucket_size : size * (i + 1) // bucket_size] for i in range(bucket_size)]def __init__(self, a: Iterable[T] = []) -> None:"Make a new SortedMultiset from iterable. / O(N) if sorted / O(N log N)"a = list(a)if not all(a[i] <= a[i + 1] for i in range(len(a) - 1)):a = sorted(a)self._build(a)def __iter__(self) -> Iterator[T]:for i in self.a:for j in i: yield jdef __reversed__(self) -> Iterator[T]:for i in reversed(self.a):for j in reversed(i): yield jdef __len__(self) -> int:return self.sizedef __repr__(self) -> str:return "SortedMultiset" + str(self.a)def __str__(self) -> str:s = str(list(self))return "{" + s[1 : len(s) - 1] + "}"def _find_bucket(self, x: T) -> List[T]:"Find the bucket which should contain x. self must not be empty."for a in self.a:if x <= a[-1]: return areturn adef __contains__(self, x: T) -> bool:if self.size == 0: return Falsea = self._find_bucket(x)i = bisect_left(a, x)return i != len(a) and a[i] == xdef count(self, x: T) -> int:"Count the number of x."return self.index_right(x) - self.index(x)def add(self, x: T) -> None:"Add an element. / O(√N)"if self.size == 0:self.a = [[x]]self.size = 1returna = self._find_bucket(x)insort(a, x)self.size += 1if len(a) > len(self.a) * self.REBUILD_RATIO:self._build()def discard(self, x: T) -> bool:"Remove an element and return True if removed. / O(√N)"if self.size == 0: return Falsea = self._find_bucket(x)i = bisect_left(a, x)if i == len(a) or a[i] != x: return Falsea.pop(i)self.size -= 1if len(a) == 0: self._build()return Truedef lt(self, x: T) -> Union[T, None]:"Find the largest element < x, or None if it doesn't exist."for a in reversed(self.a):if a[0] < x:return a[bisect_left(a, x) - 1]def le(self, x: T) -> Union[T, None]:"Find the largest element <= x, or None if it doesn't exist."for a in reversed(self.a):if a[0] <= x:return a[bisect_right(a, x) - 1]def gt(self, x: T) -> Union[T, None]:"Find the smallest element > x, or None if it doesn't exist."for a in self.a:if a[-1] > x:return a[bisect_right(a, x)]def ge(self, x: T) -> Union[T, None]:"Find the smallest element >= x, or None if it doesn't exist."for a in self.a:if a[-1] >= x:return a[bisect_left(a, x)]def __getitem__(self, x: int) -> T:"Return the x-th element, or IndexError if it doesn't exist."if x < 0: x += self.sizeif x < 0: raise IndexErrorfor a in self.a:if x < len(a): return a[x]x -= len(a)raise IndexErrordef index(self, x: T) -> int:"Count the number of elements < x."ans = 0for a in self.a:if a[-1] >= x:return ans + bisect_left(a, x)ans += len(a)return ansdef index_right(self, x: T) -> int:"Count the number of elements <= x."ans = 0for a in self.a:if a[-1] > x:return ans + bisect_right(a, x)ans += len(a)return ans###セグメントツリー########segfunc#####def segfunc(x, y):return x + y# 最小値 min(x, y)# 最大値 max(x, y)# 区間和 x + y# 区間積 x * y# 最大公約数 math.gcd(x, y)# 排他的論理和 x ^ y######################ide_ele#####ide_ele = 0# 最小値 float('inf')# 最大値 -float('inf')# 区間和 0# 区間積 1# 最大公約数 0# 排他的論理和 0#################class SegTree:"""init(init_val, ide_ele): 配列init_valで初期化 O(N)update(k, x): k番目の値をxに更新 O(logN)query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)"""def __init__(self, init_val, segfunc, ide_ele):"""init_val: 配列の初期値segfunc: 区間にしたい操作ide_ele: 単位元n: 要素数num: n以上の最小の2のべき乗tree: セグメント木(1-index)"""n = len(init_val)self.segfunc = segfuncself.ide_ele = ide_eleself.num = 1 << (n - 1).bit_length()self.tree = [ide_ele] * 2 * self.num# 配列の値を葉にセットfor 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番目の値をxに更新k: index(0-index)x: update value"""k += self.numself.tree[k] = xwhile k > 1:self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])k >>= 1def query(self, l, r):"""[l, r)のsegfuncしたものを得るl: index(0-index)r: index(0-index)"""res = self.ide_elel += self.numr += self.numwhile l < r:if l & 1:res = self.segfunc(res, self.tree[l])l += 1if r & 1:res = self.segfunc(res, self.tree[r - 1])l >>= 1r >>= 1return res###UnionFind###class UnionFind:"""0-indexed"""def __init__(self, n):self.n = nself.parent = [-1] * nself.__group_count = n # 辺がないとき、連結成分はn個ありますdef unite(self, x, y):"""xとyをマージ"""x = self.root(x)y = self.root(y)if x == y:return 0self.__group_count -= 1 # 木と木が合体するので、連結成分数が1減りますif self.parent[x] > self.parent[y]:x, y = y, xself.parent[x] += self.parent[y]self.parent[y] = xreturn self.parent[x]def is_same(self, x, y):"""xとyが同じ連結成分か判定"""return self.root(x) == self.root(y)def root(self, x):"""xの根を取得"""if self.parent[x] < 0:return xelse:self.parent[x] = self.root(self.parent[x])return self.parent[x]def size(self, x):"""xが属する連結成分のサイズを取得"""return -self.parent[self.root(x)]def all_sizes(self) -> List[int]:"""全連結成分のサイズのリストを取得 O(N)"""sizes = []for i in range(self.n):size = self.parent[i]if size < 0:sizes.append(-size)return sizesdef groups(self) -> List[List[int]]:"""全連結成分の内容のリストを取得 O(N・α(N))"""groups = dict()for i in range(self.n):p = self.root(i)if not groups.get(p):groups[p] = []groups[p].append(i)return list(groups.values())def group_count(self) -> int:"""連結成分の数を取得 O(1)"""return self.__group_count # 変数を返すだけなので、O(1)です###素因数分解###def prime_factorize(n: int) -> list:return_list = []while n % 2 == 0:return_list.append(2)n //= 2f = 3while f * f <= n:if n % f == 0:return_list.append(f)n //= felse:f += 2if n != 1:return_list.append(n)return return_list###n進数から10進数変換###def base_10(num_n,n):num_10 = 0for s in str(num_n):num_10 *= nnum_10 += int(s)return num_10###10進数からn進数変換###def base_n(num_10,n):str_n = ''while num_10:if num_10%n>=10:return -1str_n += str(num_10%n)num_10 //= nreturn int(str_n[::-1])###複数の数の最大公約数、最小公倍数###from functools import reduce# 最大公約数def gcd_list(num_list: list) -> int:return reduce(gcd, num_list)# 最小公倍数def lcm_base(x: int, y: int) -> int:return (x * y) // gcd(x, y)def lcm_list(num_list: list):return reduce(lcm_base, num_list, 1)###約数列挙###def make_divisors(n):lower_divisors, upper_divisors = [], []i = 1while i * i <= n:if n % i == 0:lower_divisors.append(i)if i != n // i:upper_divisors.append(n//i)i += 1return lower_divisors + upper_divisors[::-1]###順列###def nPr(n, r):npr = 1for i in range(n, n-r, -1):npr *= ireturn npr###組合せ###def nCr(n, r):factr = 1r = min(r, n - r)for i in range(r, 1, -1):factr *= ireturn nPr(n, r)//factr###組合せMOD###def comb(n,k):nCk = 1MOD = 10**9+7for i in range(n-k+1, n+1):nCk *= inCk %= MODfor i in range(1,k+1):nCk *= pow(i,MOD-2,MOD)nCk %= MODreturn nCk###回転行列###def RotationMatrix(before_x, before_y, d):d = math.radians(d)new_x = before_x * math.cos(d) - before_y * math.sin(d)new_y = before_x * math.sin(d) + before_y * math.cos(d)return new_x, new_y###ダイクストラ###def daikusutora(N, G, s):dist = [INF] * Nque = [(0, s)]dist[s] = 0while que:c, v = heappop(que)if dist[v] < c:continuefor t, cost in G[v]:if dist[v] + cost < dist[t]:dist[t] = dist[v] + costheappush(que, (dist[t], t))return distimport sysfrom sys import stdinfrom fractions import Fractionimport mathfrom math import ceil, floor, sqrt, pi, factorial, gcdfrom copy import deepcopyfrom collections import Counter, deque, defaultdictfrom heapq import heapify, heappop, heappushfrom itertools import accumulate, product, combinations, combinations_with_replacement, permutationsfrom bisect import bisect, bisect_left, bisect_rightfrom functools import reduce, lru_cachefrom decimal import Decimal, getcontext, ROUND_HALF_UPdef i_input(): return int(stdin.readline())def i_map(): return map(int, stdin.readline().split())def i_list(): return list(i_map())def s_input(): return stdin.readline()[:-1]def s_map(): return s_input().split()def s_list(): return list(s_map())def lcm(a, b): return a * b // gcd(a, b)def get_distance(x1, y1, x2, y2):d = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)return ddef rotate(table):n_fild = []for x in zip(*table[::-1]):n_fild.append(x)return n_fildsys.setrecursionlimit(10 ** 7)INF = float('inf')MOD = 10 ** 9 + 7MOD2 = 998244353alpa = 'abcdefghijklmnopqrstuvwxyz'ALPA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'def main():N, P = i_map()nums = [[] for i in range(N+1)]for i in range(2, N+1):for j in range(i, N+1, i):nums[j].append(i)juge = [False] * (N+1)flag = [False] * (N+1)que = deque()start = prime_factorize(P)for i in start:que.append(i)juge[i] = Trueflag[i] = Truewhile que:p = que.popleft()for i in range(1, N+1):nxt = p * iif nxt > N:breakif flag[nxt]:continueflag[nxt] = Truefor j in nums[nxt]:if juge[j] == False:que.append(j)juge[j] = Trueprint(sum(flag))if __name__ == '__main__':main()