くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU
トップ > AtCoder > Python3で解く AtCoder Beginner Contest 174 C - Repsept

Python3で解く AtCoder Beginner Contest 174 C - Repsept

AtCoder 競プロ ABC-C 等比数列の和 mod

問題は7, 77, 777 ... を純粋に並べようとするとTLEになってしまう。累乗の計算量というのはかなり大きいので、制約が大きい時はつかえないというのがポイント（知らなかったOrz）。あとは、あまりの話なので大きい数の余りを計算するのではなく余りを定数倍してその余り計算してというモジュラの性質を活用する。

概要

問題

  1. {\displaystyle k}が与えられる。
  2. {\displaystyle 7, 77, 777, ...}のように7が連続する数値の中で一番最初にkで割り切れるのは何番目（別の言い方ならいくつ7が連続する数値）か？

解くときに考えた内容

  • 累乗の計算がここまでとは思っていおらず。愚直に{\displaystyle 7, 77, 777, ...}を順番に書いて{\displaystyle k}で割るということをやると、テスト段階で計算が終わらない。。。
  • {\displaystyle 7, 77, 777, ...}は、初項7, 公比10なので、{\displaystyle i}番目は{\displaystyle \frac{7 \times (1-10^i)}{(1-10)}}と表せ、これが{\displaystyle k}で割り切れる最小の{\displaystyle i}を求めたい。
  • つまり{\displaystyle 7 \times (10^i - 1)}が{\displaystyle 9k}で割り切れる最小の{\displaystyle i}を求める。
  • この時{\displaystyle k}が7で割り切れるかどうかでパターン分けする。
    • {\displaystyle k}が7で割り切れる場合は{\displaystyle (10^i)}を{\displaystyle \frac{9k}{7}}で割って余りが1になるか
    • {\displaystyle k}が7で割り切れない場合は{\displaystyle (10^i)}を{\displaystyle 9k}で割って余りが1になるか
  • 単純に10倍していけばいいだけなので、余りを計算する時は一つ手前の計算の余りを10倍して、条件によって{\displaystyle \frac{9k}{7}}や{\displaystyle 9k}で割った余りを出していくようにしないと、巨大すぎて計算を間違えたり、そもそも計算できなくなる。

反省点

累乗の計算は計算量がかなりかかる。求めたいものは余りの計算値なので、ものすごい大きい数を使う場合は定数倍で扱えるように変形して、モジュラの性質をうまく使う必要があるということに気づけないとだめだった。

コード

AC：等比数列の和とモジュラの性質を使った方法
k = int(input())
flag = True
# 等比数列の和
# 初項7 公比10 
# 7 * (1-10**i) / (1-10)
# 7*(10**i-1)/9
# これをkで割りきれるか
# 7*(10**i-1) を 9*kで我りきれるか
# kが7倍数かそうでないかで条件分ける
# 割った余りを保持しておいて10倍してまた割るを繰り返す
mod = 1
for i in range(1, 10**6+1):
    mod *= 10
    if k % 7 == 0:
        mod = mod % (9*k/7)
        if mod == 1:
            print(i)
            flag = False
            break
    else:
        mod = mod % (9*k)
        if mod == 1:
            print(i)
            flag = False
            break
if flag:
    print('-1')
TLE/WA：愚直にやろうとする方法
k = int(input())
flag = True
ratio = 0
for i in range(1, 10**6+1):
    # flaotの桁の問題でOverflowError: integer division result too large for a floatになる。
    # ならないにしても間違える。
    sevens = 7 * (1-10**i) / (1-10)
    # こっちは遅すぎてどうしょうもない
    # サンプルすら終わらない
    # sevens = int('7'*i)
    mod = sevens % k
    if mod == 0:
        print(i)
        flag = False
        break
if flag:
    print('-1')