初投稿です。投稿の練習を兼ねています。

ATCoder ABC334 のＢ問題 "Christmas Trees" で躓きました。B問題なのにやたら難しく、悔しかったので負数の除算・剰余算について考察してみました。

Python の場合

Python で次のコードを実行してみます。

Python

print("-5//3=", -5//3)
print("-5%3=", -5%3)

結果はこうなります。「-5//3= -2」のあたり、直感的には少し違和感を感じます。

結果

-5//3= -2
-5%3= 1

-5 〜 5 の範囲で結果を一覧にしてみるとこうなります。規則的に変化しており、負の数の除算・剰余算が上のような結果になった理由が納得できます。

i	-5	-4	-3	-2	-1	0	1	2	3	4	5
i//3	-2	-2	-1	-1	-1	0	0	0	1	1	1
i%3	1	2	0	1	2	0	1	2	0	1	2

C++ の場合

C++ で次のコードを実行してみます。

C++

    cout << "-5/3= " << -5/3 << endl;
    cout << "-5%3= " << -5%3 << endl;

gcc 13.2.0 の場合の結果はこうなります。直感的にはこちらのほうが合っているような気分になります。

結果

-5/3= -1
-5%3= -2

ところが、-5 〜 5 の範囲で結果を一覧にしてみるとこうなります。

i	-5	-4	-3	-2	-1	0	1	2	3	4	5
i/3	-1	-1	-1	0	0	0	0	0	1	1	1
i%3	-2	-1	0	-2	-1	0	1	2	0	1	2

i=0 の前後で除算・剰余算の振る舞いが不自然になっていて、正・負によって計算結果に連続性がありません。そもそもC言語の言語仕様では負数の除算についての定義が無く、実装依存とされてきた歴史からこのようになっているらしいです。現実には上のような振る舞いが C/C++言語の標準になっているようですが、連続した数列を扱うときに正・負で場合分けする必要が出てきたり、面倒なことが起こります。

動作の違いについてまとめると、Pythonの除算は常に値の小さい方（数直線では左側）に丸めるのに対して、C/C++の除算は０に近い方（数直線上では0に近い側）に丸める動きをする、と言えると思います。（AtCoderのsnuke氏の解説の受け売りです） Pythonは実用的、C/C++は教科書的な振る舞いとも言えるでしょうか？（ちょっと無理あり）

マクロ

対策として、Python と同じ振る舞いになるようにマクロを作りました。

C++

// Pythonと同じ動きの除算
#define pydiv(a,b) ((0<(a)&&0<(b)||(a)<0&&(b)<0) ? (a)/(b) : (0<(b)) ? ((a)-(b)+1)/(b) : ((a)-(b)-1)/(b))
 
// Pythonと同じ動きの剰余算
#define pymod(a,b) ((0<(a)&&0<(b)||(a)<0&&(b)<0) ? (a)%(b) : ((a)%(b)+(b))%(b))

このマクロを使って試してみます。

C++

    for (int i=-5; i<=5; i++) {
        cout << i << " " << pydiv(i, 3) << " " << pymod(i, 3) << endl;
    }

結果は下のようになり、Python と同じ振る舞いになりました。

i	-5	-4	-3	-2	-1	0	1	2	3	4	5
i/3	-2	-2	-1	-1	-1	0	0	0	1	1	1
i%3	1	2	0	1	2	0	1	2	0	1	2

除算については floor() 関数などもあるので、別の良い方法もあるかもしれません。

例題

さて、躓いたAtCoderのABC334のB問題です。

解説動画では正・負を考慮せずに済むように「座標系をずらす」工夫で面倒な処理を回避していますが、あまり深く考えず、次のように書いて正答できました。

abc343_b

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pydiv(a,b) ((0<(a)&&0<(b)||(a)<0&&(b)<0) ? (a)/(b) : (0<(b)) ? ((a)-(b)+1)/(b) : ((a)-(b)-1)/(b))
#define pymod(a,b) ((0<(a)&&0<(b)||(a)<0&&(b)<0) ? (a)%(b) : ((a)%(b)+(b))%(b))

int main()
{
    ll A, M, L, R;
    cin >> A >> M >> L >> R;
    L -= A;
    R -= A;
    cout << pydiv(R,M) - pydiv(L-1,M) << endl;
    return 0;
}

追記

コメント欄で @Nabetani さんからinline関数を使った実装を提案いただきました。C++の作法としてはこちらのほうが良いかもしれません。改行を省いて各1行で書いておけば競プロ用のヘッダーファイルに書いておいても邪魔になりません。
@Nabetani さん、ありがとうございました。

C++

template< typename T > inline auto pymod2( T const & a, T const & b ) -> decltype(a%b) { return (a%b+b)%b; }
template< typename T > inline auto pydiv2( T const & a, T const & b ) -> decltype(a/b){ return (a-pymod2(a,b))/b; }

また、@fujitanozomu さんからは次のような実装を提案いただきました。

C++

template< typename T >
inline T pymod3(T a, T b) {
    return ((a ^ b) < 0) && a % b != 0 ? a % b + b : a % b;
}

template< typename T >
inline T pydiv3(T a, T b) {
    return ((a ^ b) < 0) && a % b != 0 ? a / b - 1 : a / b;
}

どちらのご提案も勉強になりましたが、自分自身のテンプレートには、最初に書いた自分のマクロを採用することにしました。他人に強く勧めるものではありませんが、「結果が負になるときは数直線上で左側に丸める」という自分の思考に一番近いからです。コメントをいただいたお二人には感謝申し上げます。