AtCoder Beginner Contest 144 過去問 (A~C)

参照

atcoder.jp

A問題

特に問題なく。

a,b=map(int,input().split())
if 0<a<10 and 0<b<10:print(a*b)
else: print('-1')

B問題

C問題と似たように約数列挙。
こちらは制約が緩く、簡単でした。

def make_divisor(n):
  divisors=[]
  for i in range(1,int(n**0.5)+1):
    if n%i==0:
      divisors.append([n//i,i])
  return divisors
 
n = int(input())
lis = make_divisor(n)
for j in lis:
  if j[0]<10 and j[1]<10:
    print('Yes')
    exit(0)
print('No')

C問題

B問題でもC問題でも役に立った考え方ですが、
約数の列挙を行いました。

qiita.com

計算量 O(√N))であるので、
標準的な約数列挙法よりも高速で行えます。

C問題では2≤N≤10**12なので、
適用できるか微妙なライン(最大計算量 : 10**6)でした。
結果的には問題なくACされました。

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
           divisors.append(i+n//i)
    return divisors
 
n = int(input())
lis = make_divisors(n)
print(min(lis)-2)