問題 解説 と書き直すとは互いに素。また，。これらをに代入して整理すると ここでの素因数分解を考える。 が素数のとき のときのみ条件を満たすが，は自然数より条件を満たすようなは存在しない。 のとき すべてののとき ，つまり，は互いに素となり，なの…

３ 最小公倍数と最大公倍数 最小公倍数と最大公約数の利用 たてＡ cm, 横Ｂ cm, 高さＣ cmの直方体がたくさんある。この箱を隙間なく並べて立方体を作る。作ることができる最小の立方体の1辺の長さを求めよ。 Ａ,Ｂ,Ｃの最小公倍数を求めればよい。最小公倍…

2 素因数分解の利用 素因数の個数 2で割り切れる回数 自然数Ｎに対して，１～Nまでの自然数の積をPとする。 (1)Pが2で何回割り切れるか。 愚直な実装をすれば，素直に2で割り続ければよい。 def func(n): if n == 1: return 1 return n*func(n-1) N = int(in…

マスター・オブ・整数とは マスター・オブ・整数とは，雑誌「大学への数学」の分野別充填シリーズ。主に難関大学を目指す高校生向けの書籍である。 競技プログラミングに高校数学の整数分野の知識，テクニックが役に立つとよく聞くので冬休みを利用して解き…

再帰関数と全探索の勉強 問題 atcoder.jp 参考にしたサイト qiita.com qiita.com いずれもこの方のページ。他にもたくさん競プロ向け記事を書いていらっしゃいます。 qiita.com 考察（とりあえず再帰を使ってみる） 全探索と再帰の勉強のための解きなおしな…

問題 atcoder.jp N人の正直者（必ず本当のことを言う）か不誠実な人（本当のことを言うかわからない）がいる。N人の人が〇〇さんは正直者（または不誠実な人）だよと証言する。証言が矛盾しない範囲で，最大で何人の正直者がいるかを求めよ。 試行錯誤（全探…

今日もyukicoder 問題 yukicoder.me 入力で与えられた数が「素数,1,使う数自身」以外で割り切れるかどうかを判定する。 考え方 1はダメ。素数もダメ，入力で与えられた数Nもダメ。それ以外の数字で割り切れればＯＫということなので，合成数の約数を持つかど…

※noteに記事を投稿していましたが，数式を書きたくなることがたまにあるのでHatena Blogも試してみることにしました。 note.com 下記問題に挑戦した。問題詳細は以下。 yukicoder.me 愚直に実装したらTLEでした（そりゃそうだ）。 x, N = map(int,input().sp…