AtCoder-ARC113 A - A*B*C / B - A^B^C【Python解答例】

AtCoderのARC113に参加しましたがひとつも解けませんでした…
めっちゃへこんでますが、がんばってAとB問題を復習していきます。
AtCoder Regular Contest 113 - AtCoder

AtCoder Regular Contest113 A - A*B*C

A - A*B*C

問題文

正の整数 K が与えられます。正の整数の 3 つ組 (A,B,C) であって、ABC≤K なるものの個数を求めてください。
ただし、A,B,C の順番が異なるだけの組も異なる組として数えます。

制約

・1≤K≤2×10^5
・K は整数である

解答例

k = int(input())

ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        if i * j > k:
            break
        ans += k // (i * j)
print(ans)

解説

A,B,CをそれぞれKまで全探索すると間にあわないので、AとBを全探索しました。
コンテスト中はそれでも間にあわないと思ってましたが、A × B < k に限れば間にあうようです。
（調和級数という初めて聞いた言葉がキーワードのようです）

候補となるA × Bがみつかれば C は K を A × B で割った商の数だけあるので、その値をansに足していきました。

ループを抜けてansを出力すればOKでした。

AtCoder Regular Contest113 B - A^B^C

B - A^B^C

問題文

正の整数 A,B,C が与えられます。A^B^C の 10 進法での 1 の位を求めてください。

制約

・1≤A,B,C≤10^9
・A,B,C は整数である

解答例

a, b, c = map(int,input().split())

bc = pow(b, c, 4)
if bc == 0:
    bc = 4
ans = pow(a, bc, 10)
print(ans)

解説

A,B,Cが10^9と大きいためそのまま計算するとTLEとなってしまいました。

整数Nに対して累乗の1の位は規則的に同じ数があられ、その周期は4になるようです。（解説をみて知りました…）
したがって、B^Cを4で割った余りをMとすると、A^B^Cと A^Mの1の位は同じになります。

これで累乗の数をちいさくできるので制限時間内に解くことができるようになりました。

残念ながらひとつも問題は解けませんでしたが勉強になることばかりでした。
Twitterでもいろんな方から教えていただくことができて本当にありがたく思っています。

初心者の僕は下がることを心配するレートもありませんので、数多く参加して学んでいくことが大事だなって思えるコンテストでした。
決してひとつも解けなかったことへの負け惜しみではないと思ってます (^_^;)