競プロ精進日記 #1

競技プログラミング-精進日記

精進や復習で解いた問題を列挙していきます。

AtCoder

  • ABC162 E Sum of gcd of Tuples (Hard)
    提出したソースコード
    解き方は理解できたけど、自分の考え方だとどうして上手くいかないのかは謎のまま。。。
    gcd(a_1, a_2, ... , a_n) が x の倍数となるのは a_1, a_2, ... , a_n が x の倍数のときというのは気づけていた。
    そうしたら、 a_1, a_2, ... , a_n のうち最低 1 つが x であれば良いのではと考えた。
    余事象的な考え方をして、 求める個数は num = k / x として、
    num^n - (num - 1)^n ではダメなのだろうか。。。
    どなたか教えてください。。。

yukicoder