AtCoder Beginner Contest 227 B

https://atcoder.jp/contests/abc227/tasks/abc227_b

第一感は、 $4ab+3a+3b$ を列挙してsetにするでした。

def F_naive(S):
    M = max(S)
    possible_areas = set(4*a*b + 3*a + 3*b
                            for a in range(1, (M - 3) / 7 + 1)
                            for b in range(1, (M - 3*a) / (4*a + 3) + 1))
    
    return sum(1 for area in S if area not in possible_areas)

計算量を調べるためにsetに入れる値の数のオーダーを調べます。
Sの上限を便宜上Sと書くこととして、aを固定すると、bの取り得る値の数は、 $\frac{S-3a}{4a+3}$ なので、
$\displaystyle \sum_{a=1}^{\frac{S-3}{7}}{\frac{S-3a}{4a+3}} \approx \int_1^{\frac{S-3}{7}}{\frac{S-3a}{4a+3}da} \approx \int_1^{\frac{S}{7}}{\frac{S}{4a}da} \approx \frac{S}{4}log{\frac{S}{7}}$

重複があるので、setに入る値の個数を概算します。
$S = 4ab + 3a + 3b$
$4S + 9 = (4a + 3)(4b + 3)$
なので、 $4S+9$ が7以上の4で割って余り3の自然数同士の積で表されれば $S$ に対応する $a, b$ が存在することになります。
Sになる割合をプロットしてみましょう。

# Python3
from itertools import *
import matplotlib.pyplot as plt

S = 10**7
s = set(4*a*b + 3*a + 3*b for a in range(1, (S - 3) // 7 + 1)
                          for b in range(1, (S - 3*a) // (4*a + 3) + 1))
v = sorted(s)

xs = [ 10**e for e in range(2, 8) ]
ys = [ sum(1 for n in takewhile(lambda n: n <= x, v)) / x for x in xs ]
print(ys)

fig, ax = plt.subplots()
ax.plot(xs, ys, 'o')
plt.xscale('log')
ax.ticklabel_format(style='sci', axis='y')
plt.savefig('ABC227B.png')

f:id:inamori:20211118191328p:plain

割合は段々高くなるように見えます。大きいほうが約数が多くなるので当然ですね。結局、set内の値の個数は $O(S)$ になります。
Nの上限をここではNと書くとすると、トータルの計算量は $O(S\log{S} + N\log{S})$ となります。 $S=10^6$ 程度ならこのアルゴリズムで十分です。

Sが大きくてNが小さいときは、一つのSについて4S+9を7, 11, …と割っていけばよいでしょう。計算量は $O(N\sqrt{S})$ となります。

def F(S):
    def is_divisible(n):
        if n < 49:
            return False
        
        return any(n % d == 0
                    for d in takewhile(lambda d: d*d <= n, count(7, 4)))
    
    return sum(1 for s in S if not is_divisible(4*s+9))