BOJ-1612-玩的1

3714 ワード
math algorithm boj テキストリンク

必要な知識

  • 数学

    • に近づく

  • nの倍数では、1からなる数の中で最小の桁数しか出力できません.ない場合は-1を出力します.

  • 不可能な場合、1のみからなる数は、約2および5である.したがって、nが入力されると、2または5に分割されると、-1が出力される.
  • 1のみからなる倍数を解く場合、1111を確認して*10+1を行い、11111を生成して計算すると、1のみからなる倍数の大きさが大きくなりすぎる.
  • 1のみからなる倍数を格納する変数は、nを使用してモジュール化された演算を継続し、数字が大きすぎることを回避します.

  • 動的計画法でよく用いられる方法はモジュール化演算であるが,この方法は考えるまでに長い時間がかかる.

    • コード(C+)

    #include <iostream>
using namespace std;
int main() {
	int n, ans = 1, tmp = 1; cin >> n;
	if (n % 2 == 0 || n % 5 == 0) {
		cout << "-1" << "\n";
		return 0;
	}
	while ((tmp % n) != 0) {
		ans += 1;
		tmp = (tmp % n) * 10 + 1;
	}
	cout << ans << "\n";
	return 0;
}

    結果


    例
    リスト内の要素とコピー