素数判定
素数判定。鉄則本の問題なので、コードのみ。 問題へのリンク 問題概要 個の整数 がそれぞれ素数であるかどうかを判定せよ。 制約 コード #include <bits/stdc++.h> using namespace std; bool is_prime(int N) { if (N <= 1) return false; for (int x = 2; x * x <= N; x+</bits/stdc++.h>…
Miller-Rabin 法や、モンゴメリ乗算を試せる問題ですね！ 問題へのリンク 問題概要 クエリが 個与えられる。 各クエリでは正整数 が与えられるので、素数かどうか判定せよ。 制約 解法 Miller-Rabin 法が使える。次のようなアルゴリズムである。 のとき：素…
ミラー・ラビンの素数判定法は、その背景にある整数論的考察もめっちゃ面白いので、ぜひそれも味わいましょう！！ 1. はじめに 本記事では正の整数 が与えられたときに、 が素数であるか否かを判定する問題を考えます。 よく知られた方法は、 を で順に試し…
JOI
JOI春合宿
JOI難易度5
数学(整数問題)
素因数分解
考察：独立に考えてよい
素数
pで何回割れるか
素数判定
場合分け
O(√N)まで考えれば十分
平方分割
各素因数ごとに考える
ルジャンドルの定理
N!に関する問題
素因数分解ゲー！ 今なら ABC D あたりに出てきそう (実際に出てきた！) ジャッジページ 問題文 問題概要 正の整数 が与えられる。 が の倍数となるような最小の正の整数 を求めよ。 制約 解法 以下の記事の問題と全く同じです。詳しい解法はこの記事に書き…
