ABC060-B 備忘録 p.8

itsukiです。
AtCoderの過去問を解いた様子です。解説記事ではありません。

B - Choose Integers

考察の流れ

総和っていうけど「Aの倍数」である以上、いくら足しても「Aの倍数」になる

N*A mod B = C となるNを全探索してみる
…どこまで探索したら完了なんだ？

入力例1（A=7, B=5, C=1）で考えてみる
7mod5=2
14mod5=4
21mod5=1
28mod5=3
35mod5=0
42mod5=2
49mod5=4
56mod5=1
63mod5=3
2, 4, 1, 3, 0, …ってループしてる、 bと同じ数だけループするのか？

もしそうだとしたら他の入力例は手作業厳しそうだから、とりあえずプログラム組んで試してみるか（安易）

#include <stdio.h>
int main(){
    int a,b,c;
    scanf("%d%d%d", &a,&b,&c);
    for(int i=1; i<=b; i++){
        if( (i*a) % b == c ){ printf("YES\n"); return 0; }
    }
    printf("NO\n");
    return 0;
}

まとめ

・サンプルが通ってしまったのでとりあえず投げてみたらAC
・ちゃんと分かってないのにとりあえず投げる癖、本番だとペナルティ原因になるから直さなきゃと思いながら投げてしまう

引き続き、のんびり精進します。

#note初心者 #備忘録 #AtCoder #ABC #競技プログラミング #競プロ #数学   #C言語 #mod #倍数 #全探索