A – 9×9
1 2 3 4 5 |
a,b = map(int, input().split()) if 1 <= a <=9 and 1 <= b <=9: print(a*b) else: print(-1) |
C – Walk on Multiplication Table
方針
・10**12なので全探索はできない。でも10**6は計算量の制約から見て収まりが良さそう
・i×j>nとなってはならないため、i,jの最大値はどちらもnの平方根(sqrt(n))となる
・1からsqrt(n)までで条件を満たす組み合わせがあるか調べる
・i*j=nになる(i,j)の組み合わせのうち、i+jの最小値を調べる
・初期位置は(1,1)なので、i,jからそれぞれ1を引いた数の合計を出力する
解答
コード+コメント
1 2 3 4 5 6 7 8 9 10 11 12 13 |
n = int(input()) #最小値を調べるのでnで初期化 ans = n #1からnの平方根+1まで調べる for i in range(1,int(n**0.5)+1): #nをiで割り切れるなら if n%i==0: #jにn÷iを代入。i×n=j → j=i÷n j = n//i #現在の最小値と比較して小さい方をansへ ans = min(i+j-2,ans) #出力 print(ans) |
コードのみ
1 2 3 4 5 6 7 |
n = int(input()) ans = n for i in range(1,int(n**0.5)+1): if n%i==0: j = n//i ans = min(i+j-2,ans) print(ans) |
その他
他のABC解説記事一覧
【Python】AtCoder Beginner Contest 解答・解説記事一覧
コメント