典型90問
038 - Large LCM（★3）
- gcdを使って以下の様に愚直にlcmを実装したら案の定オーバーフローしてWA
long long lcm(long long x, long long y) {
return x / gcd(x, y) * y;//先に割り算をして掛けられる数を小さくして掛け算を行う
}
int main() {
long long A,B;
cin >> A >> B;
if (lcm(A,B) > 1e18){
cout << "Large" << endl;
} else {
cout << lcm(A,B) << endl;
}
}
- 以下の様にオーバーフローしないかをチェックする。単純に
a*b > limitにするとオーバーフローを回避できないのでa > limit / bの様に上手く移項して確認する。数学的には不等式の割り算には注意が必要だがこれは入力の制約を見れば問題なし
bool will_overflow(long long a, long long b, long long limit) {
return a > limit / b; // a * b > limit なら true
}
044 - Shift and Swapping（★3）
- 流石に難しかった。
- 見かけ上の変化をメモするらしい。T＝2でシフトする際に実際にシフトされるのではなくT＝2が連続で呼ばれた回数をカウントした上でT=1,T=3においてその回数分動かした程で答えを出せば計算量を減らせる。
046 - I Love 46（★3）
- 理解はできたが解説を一度読んだだけではわからなかった。というか解答例になっているソースを読んだ方が分かりやすかった
- 要は
A + B + Cが46の倍数になるということはA,B,Cをそれぞれ46で割った余りを足したものが46で割り切れる必要がある。よってA,B,Cを46で割った余りの個数を配列に格納して（0~45）の46通りそれぞれのあまりの組み合わせ46³を全探索してそれらの和が46で割り切れるかをチェック→割り切れるならそれらの個数を掛けたものを答えの変数に足していく。
これで3 * 10⁵ + 46³の計算量で答えを出せる。