-
Notifications
You must be signed in to change notification settings - Fork 6
/
numbersetshard.py
42 lines (40 loc) · 1.17 KB
/
numbersetshard.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class UFDS:
def __init__(self, N):
self.p = [*range(N)]
self.rank = [0]*N
self.n = N
def find_set(self, i):
if self.p[i] == i: return i
self.p[i] = self.find_set(self.p[i])
return self.p[i]
def is_same_set(self, i, j):
return self.find_set(i) == self.find_set(j)
def union(self, i, j):
if not self.is_same_set(i, j):
self.n -= 1
x, y = self.find_set(i), self.find_set(j)
if self.rank[x] > self.rank[y]: self.p[y] = x
else:
self.p[x] = y
if self.rank[x] == self.rank[y]: self.rank[y] += 1
LIMIT = 10**6
spf = list(range(LIMIT+1))
primes = [2]
p = 3
while p <= LIMIT:
if spf[p] == p:
primes.append(p)
for i in range(p*p, LIMIT+1, 2*p):
if spf[i] == i: spf[i] = p
p += 2
primes = primes[::-1]
input()
import sys; t = 1
for l in sys.stdin:
a, b, p = map(int, l.split())
u = UFDS(b-a+1)
for pp in primes:
if pp < p: break
lo = (a+pp-1)//pp*pp
for c in range(lo+pp, b+1, pp): u.union(lo-a, c-a)
print(f'Case #{t}:', u.n); t += 1