I was so sleepy that I took a nap for 20 minutes just before and did my best.

aising2020A - Number of Multiples

Break through in one and a half minutes. Just write according to the conditions of the problem. It takes time, so I do not think about solving it with * O * (1).

```
L, R, d = map(int, input().split())
result = 0
for i in range(L, R + 1):
if i % d == 0:
result += 1
print(result)
```

Postscript: * O * (1)

```
L, R, d = map(int, input().split())
print(R // d - (L - 1) // d)
```

Break through in 2 minutes. Just write according to the conditions of the problem.

```
N = int(input())
a = list(map(int, input().split()))
result = 0
for i in range(N):
if (i + 1) % 2 == 1 and a[i] % 2 == 1:
result += 1
print(result)
```

Postscript: I should have skipped even-numbered slices ...

```
N, *a = map(int, open(0).read().split())
print(sum(1 for e in a[::2] if e % 2 == 1))
```

It broke through in 6 and a half minutes. N ≤ 10 ^{ 4 </ sup> So I thought it would pass even in a triple loop. In fact, it passed.}

```
N = int(input())
result = [0] * (N + 1)
for x in range(1, 101):
for y in range(1, 101):
for z in range(1, 101):
n = x * x + y * y + z * z + x * y + y * z + z * x
if n > N:
break
result[n] += 1
print(*result[1:], sep='\n')
```

aising2020D - Anything Goes to Zero

I couldn't break through. When A = B * C, I thought that I could get a large number of remainders using A% m = (B% m) * (C% m)% m, so I built it using it, but TLE I'm not sure because I get the RE and the RE. The first process can be * O * (1) by pre-calculation, but what should I do after the second?

Addendum: The maximum value returned by * f * (* n *) is log _{ 2 </ sub> (}* n *), so 2

RE was originally issued when only one bit was set, and when the only set bit was inverted, * popcount * was not noticed to be 0, and it was divided by 0. TLE Was displayed in log _{ 2 </ sub> (* X *) without being aware that it was 2 × 10 5 </ sup> * O * ( N </ i> > log X </ i>) because it was written.}

Although the idea was correct, I felt that I could not solve it due to some omissions.

```
def popcount(n):
return bin(n).count("1")
def f(n):
if n == 0:
return 0
return 1 + f(n % popcount(n))
N = int(input())
X = input()
c = X.count('1')
t1 = [0] * N
t1[0] = 1 % (c + 1)
for i in range(1, N):
t1[i] = (t1[i - 1] << 1) % (c + 1)
x1 = 0
for i in range(N):
if X[i] == '0':
continue
x1 += t1[N - 1 - i]
if c - 1 != 0:
t2 = [0] * N
t2[0] = 1 % (c - 1)
for i in range(1, N):
t2[i] = (t2[i - 1] << 1) % (c - 1)
x2 = 0
for i in range(N):
if X[i] == '0':
continue
x2 += t2[N - 1 - i]
result = []
for i in range(N):
if X[i] == '0':
n = (x1 + t1[N - 1 - i]) % (c + 1)
elif X[i] == '1':
if c - 1 == 0:
result.append(0)
continue
n = (x2 - t2[N - 1 - i]) % (c - 1)
result.append(1 + f(n))
print(*result, sep='\n')
```

Recommended Posts