ABC174に参加してみた

初めに

ABC174はAB完でした。Cが緑パフォの問題でDが茶パフォの問題だったんですが、 Cに置かれたら頑張って解こうとしちゃうんですよね(笑) ということでC問題について書いていきます！

https://atcoder.jp/contests/abc174

※ブログ内で問題の制約事項をすべて記載はしないので、制約事項は↑のURLより参照願います。

C - Repsept

この問題は7,77,777,…と続く数列の中に初めて入力Kの倍数が登場するのは 何項目かを求める問題で、倍数が存在しない場合は-1を出力します。

解説を見てからの回答

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

typedef pair<ll,ll> Pair;

int main(){

ll K;


cin >> K;

ll x=7%K;

set<ll> s;
ll ans = 1;

// 同じ値が格納されていない間はループする
while(s.count(x) == 0){

  // mod計算の結果が0の場合は第何項かを出力し終了
  if(x == 0){
    cout << ans << endl;
    return 0;
  }
  // xの値を格納
  s.insert(x);
  // 掛け算・足し算の途中でmod Kの計算
  x = (x*10+7)%K;
  ++ans;
}

// Kの倍数となる数列が無い場合は-1を出力
cout << "-1" << endl;

return 0;

}   

まずは、数列がどのような規則で変化しているか確認してみると、
下記イメージのように増加している事がわかります。

イメージ

どうような規則で変化していくかはわかりましたが、上記のように数列が増えていくと
値が膨大になりオーバーフローしてしまいます。そこでmod Kを利用して考えて見ます。

足し算や掛け算の途中でmodの計算を行っても計算結果は下記の通り同じになるため
数列の値が増える度にmod Kの計算を行う事でオーバーフローせずに計算を行う事が出来ます。

イメージ

計算途中でmod Kの計算を行う事で、オーバーフローせずに計算を行えるようになりましたが、
数列にKの倍数が存在する・しないの判定をするためにはどのような条件で
処理を進める必要があるでしょうか。

下記のようにmod Kの計算で一度出現した値が出るとその後の値も同じ値の繰り返しとなります。
そのため、同じ値が出現するまでループを回しその間にmod Kの計算結果が
0になるか・ならないかでKの倍数であるかどうかを判定することが出来ます。
(mod Kで計算すれば行けそうなのは分かったんですが、判定部分がわかりませんでした、、、)

イメージ

上記の条件で計算を進めて行くことで答えを求める事が可能です。

最後に

いやー、ほんとにC問題で緑パフォが出ると無理ですね(笑)
なんとなくアプローチが分かる問題もあるんですけど、問題を解くには至らないんですよね、、、
まぁでも少しずつではあるけど、この問題ではあれが使えそうとか引き出しは
少しずつ増えてきた実感はあるので引き続き頑張りまっしょい