-
Notifications
You must be signed in to change notification settings - Fork 15
/
gallery-of-pillars.py
53 lines (48 loc) · 1.8 KB
/
gallery-of-pillars.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
43
44
45
46
47
48
49
50
51
52
53
# Copyright (c) 2019 kamyu. All rights reserved.
#
# Google Code Jam 2016 World Finals - Problem C. Gallery of Pillars
# https://code.google.com/codejam/contest/7234486/dashboard#s=p2
#
# Time: O(NlogN)
# Space: O(M)
#
from math import sqrt
def count(side_len, r_square): # Time: O(side_length) = O(N/d), Space: O(1)
# count pairs of |(x, y)|^2 <= r_square and
# 0 <= x, y <= min(side_len, int(sqrt(r_square))) and (x, y) != (0, 0)
result = 0
y = side_len
if r_square < y*y:
y = int(sqrt(r_square)) # Time: O(log(N/d))
for x in xrange(y+1):
while x*x + y*y > r_square:
y -= 1 # Time: O(N/d)
result += y+1 # (x, 0) ~ (x, y)
return result-1 # exclude (0, 0)
def gallery_of_pillars():
N, R = map(int, raw_input().strip().split())
# count pairs of |(x, y)| < M/R and 0 <= x, y <= N-1 and gcd(x, y) = 1
result = 0
r_square = (M*M-1)//(R*R)
for d in xrange(1, min(N-1, int(sqrt(r_square)))+1): # Time: sum of O(N/d) = O(NlogN), see https://math.stackexchange.com/questions/306371/simple-proof-of-showing-the-harmonic-number-h-n-theta-log-n
if MU[d]: # see https://artofproblemsolving.com/wiki/index.php/Mobius_function
result += MU[d] * count((N-1)//d, r_square//(d*d))
return result
def sieve_of_eratosthenes(n): # Time: O(Mlog(logM)), Space: O(M)
is_prime = [True]*n
mu = [1]*n
for i in xrange(2, n):
if not is_prime[i]:
continue
for j in xrange(i+i, n, i):
is_prime[j] = False
for j in xrange(i, n, i):
mu[j] = -mu[j]
if i <= n//i:
for j in xrange(i*i, n, i*i):
mu[j] = 0
return mu
M = 10**6
MU = sieve_of_eratosthenes(M)
for case in xrange(input()):
print 'Case #%d: %s' % (case+1, gallery_of_pillars())