AtCoder Beginner Contest 176 B問題「Multiple of 9」解説(Python3,C++,Java)

Ruteです。
この記事は先ほどのA問題の解説の続きになります！

##各問題・解説へのリンク

A	B	C
ABC176 A	この記事です！！	ABC176 C

それでは、B問題の解説を行います。

#問題概要
$N$が$9$の倍数であるかを判定して下さい。

##制約
・$0 \leq N \leq 10^{200000}$
・$N$は整数

今回は、Python3とC++,Javaで解法が異なりますのでご了承下さい。

#解説
##解法1(Python3の場合)
＊後で説明する解法2でも解けます。
Python3の場合は、int型で表せる整数に限度がないので、以下のような条件分岐を書くことでACすることが出来ます！
(厳密に言うと多倍長整数を扱うことが出来るということです)

{ABC176B.py}

print("Yes") if int(input())%9 == 0 else print("No")

※ここではコードを短縮しましたが、短縮しないで解いても問題ありません。

##解法2(C++,Javaの場合)
今回の制約に注目してみましょう。
・$0 \leq N \leq 10^{200000}$

そうです、$N$の範囲が$10^{200000}$までとなっています。
$10^{64}$が1無量大数なので、$10^{200000}$はとてつもなく大きな整数であるといえます。

このような整数だと、C++ではint型どころかlong long int型でも表せなくなります。
(Javaの場合だとこれがlong型になります)

そこで皆さん、$9$の倍数の性質について確認してみましょう。
まずはこちらの動画をご覧下さい。

9の倍数の性質(ネタ元:トリビアの泉)

9のかけ算の答えは数字同士を足していくと必ず9になる

これは、$9$の倍数である場合は桁和が$9$で割り切れる ということと同値になります。
(問題文にもこれと同様のことが記載されています)
つまり、桁和が$9$で割り切れるかどうかを判定する　という単純な問題に置き換えることが出来ました。桁和を求めるには文字列の長さ分の線形時間がかかりますが、制約の範囲では実行時間制限に間に合います。

以下、解法2での解答例を、Python3,C++,Javaの3言語で示します。

##各言語解答例(解法2)

Python3での解答例

{ABC176B2.py}

N = input()
ans = 0
for i in range(len(N)):
  ans += N[i]
print("Yes") if ans%9 == 0 else print("No")

C++での解答例

{ABC176B2.cpp}

#include<bits/stdc++.h>
using namespace std;
int main(){
  string s;
  cin >> s;
  int ans = 0;
  for (int i = 0; i < s.size(); i++){
    ans = ans +  int(s.at(i))-48;
  }
  if (ans%9==0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

*ASCIIコードの性質を利用して桁和を計算しました。
ASCIIコードでは'0'が48, '9'が57であるため、ASCIIコードから48を引くことで、文字列を整数に直すことができます。

Javaでの解答例

{ABC176B2.java}

import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    String S = scan.next();
    int ans = 0;
    for (int i = S.length(); i > 0 ; i--){
      ans = ans + Integer.parseInt(S.substring(i-1,i));
    }
    if (ans % 9 == 0){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  }
}