アルゴ式
- 「2つの格子点の各座標の差を取って最大公約数を取る→そこから-1した値」ということに気づけなかった。
// 最大公約数を求める関数
long long GCD(long long A, long long B) {
if (B == 0)
return A;
else
return GCD(B, A % B);
}
int main() {
long long A, B, C, D;
cin >> A >> B >> C >> D;
long long G = GCD(abs(C - A), abs(D - B));
cout << G - 1 << endl;
}
- 割ればいいだけなのに無理にfor文で求めるというコーディングにとらわれすぎ解法で一度WAしてしまった。
- さすがに自分で気づけたが...
int main() {
long long A,B,N;
cin >> A >> B >> N;
cout << N / B << endl;
}
- Ax を B の倍数に (1)の応用。A,Bが互いに素じゃない可能性を考慮して最大公約数Gで割ってしまえばAx を B の倍数に (1)に帰着できる。
- 和と積がともに整数となるa+bは3のみ
- 正の整数 Nの約数が奇数個 ⇔ Nは平方数ということに気づけば一瞬だった...
- 基本は約数というのはペアになるが唯一平方数の場合だけは異なる整数のペアにならない
- 正の整数Nが3この約数を持つ⇔ある素数pが存在してN=p^2と表せる→つまりN以下の正数のうち素数の平方で表せるものを数え上げるということに気づけなかった...
- 解説AC
- ルシャンドル関数を知りませんでした
- 解説AC
- 解説読めば理解できるなあ程度。A0の式をそれぞれから引くという発想がない
- 「題意を満たす⇔最小公倍数の約数の個数を求めること」という言いかえができなかった...
// N の約数をすべて求める関数
vector<long long> calc_divisors(long long N) {
vector<long long> res;
for (long long i = 1; i * i <= N; ++i) {
if (N % i != 0) continue;
res.push_back(i);
if (N / i != i) res.push_back(N / i);
}
sort(res.begin(), res.end());
return res;
}
int main() {
// 入力
long long N, M;
cin >> N >> M;
// M の約数の個数を答える
cout << calc_divisors(M).size() << endl;
}
- 最大公約数の種類数 (1)を応用するという意味では実質的な誘導があったから理解できるが、普通に一から答えを出すのは無理だと思う。題材は最大公約数じゃなかったがABC405のC問題とかちょっと似た考え方で解いたのを覚えている
- 解説なし問題でわからずじまいだったので仕方なくGPT先生に聞いた。
- GPT先生は天才だった。
- M/GCD が N 乗数（整数の N 乗）になっているかを確認するという観点
- 虚無
- 何の誘導もない素数判定問題（ただし高速で）かつヒント的なものもミラーラビン素数判定方のWikipediaへのリンクのみで泣く泣く解説を見るもサンプルコードと503で開けないページへのリンクだけだった...
- 虚無（ミラー-ラビンの素数判定法と同じ）
- 高速な素因数分解法だというのでどこかで使うタイミングがあれば活用したい
雑談
アルゴ式が一通り落ち着いた（上級は未着手...）ので「競技プログラミングの鉄則」を読み物として読破していたが実装まで含めてゴリゴリ身に着けていきたい。やはり読んだだけでは勝てない...