tz_atcoder/abc292_c.py at main · tztechno/tz_atcoder · GitHub

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
###############################################
###############################################
###############################################
###############################################
###############################################
###############################################
[TLE16]
n=int(input())
#ab+cd=n
AB=[]
C=[]
for ab in range(1,n):
  for a in range(1,n):
    if ab%a==0:
      b=ab//a
      AB+=[(a,b,ab)]
      C+=[ab]
t=0
ANS=[]
for abi in AB:
  a,b,ab =abi
  cd=n-ab
  if cd in C:
    for c in range(1,n):
      if cd%c==0:
        d=cd//c
        ANS+=[(a,b,c,d)]
        t+=1
print(t)

###############################################
[TLE16]
n=int(input())
#ab+cd=n
from collections import defaultdict,deque,Counter
cnt = defaultdict(list)
C=[]
for ab in range(1,n):
  for a in range(1,n):
    if ab%a==0:
      b=ab//a
      cnt[ab].append((a,b))
      C+=[ab]
#print(cnt)
t=0
#ANS=[]
for ab in cnt.keys():
  cd=n-ab
  if cd in C:
    t+=len(cnt[cd])*len(cnt[ab])
print(t)

###############################################
[TLE15]
n=int(input())
#ab+cd=n
from collections import defaultdict,deque,Counter
cnt = defaultdict(int)
for ab in range(1,n):
  for a in range(1,n):
    if ab%a==0:
      b=ab//a
      cnt[ab]+=1
#print(cnt)
t=0
#ANS=[]
for ab in cnt.keys():
  cd=n-ab
  if cd in cnt.keys():
    t+=cnt[cd]*cnt[ab]
print(t)

###############################################
[TLE15]
n=int(input())
#ab+cd=n
from collections import defaultdict,deque,Counter
cnt = defaultdict(int)
for ab in range(1,n):
  for a in range(1,n):
    if ab%a==0:
      cnt[ab]+=1
t=0
for ab in cnt.keys():
  cd=n-ab
  if cd in cnt.keys():
    t+=cnt[cd]*cnt[ab]
print(t)

###############################################
[AC]
n=int(input())

def divisor_pairs(n: int):
  pairs = []
  for a in range(1, int(n ** 0.5) + 1):
    if n % a == 0:
      b = n // a
      pairs.append((a, b))
      if a != b:
        pairs.append((b, a))
  return pairs

from collections import defaultdict,deque,Counter
cnt = defaultdict(int)
for ab in range(1,n):
  pairs=divisor_pairs(ab)
  cnt[ab]+=len(pairs)

t=0
for ab in cnt.keys():
  cd=n-ab
  if cd in cnt.keys():
    t+=cnt[cd]*cnt[ab]
print(t)


###############################################
###############################################
###############################################
###############################################
###############################################
###############################################
###############################################
###############################################
###############################################