数値型で表せないn桁整数の剰余

はじめに

AtCoderで，long long int型（64bit整数）でも表せない整数の剰余を求めるのに苦労した。そのメモ。

考え方

・long long int型（64bit整数）でも表せない整数は文字列型で表す
・剰余計算を桁ごとに分割する

関数（c++)

// str...割られる数，mod...割る数，rem...剰余，digits...桁数
using namespace std;
typedef long long ll;
const ll mod = 998244353; 

void str_rem(const string str, const ll digits, ll &rem) {
    rem = 0;
    for (ll i = 0; i < digits; i++) {
        ll p = rem * 10 + (str[i] - '0');
        rem = p % mod;
    }
}

例

#include <iostream>
using namespace std;
typedef long long ll;

const ll mod = 3;

void integer_rem(const ll num, ll &rem) { rem = num % mod; }

void str_rem(const string str, const ll digits, ll &rem) {
    rem = 0;
    for (ll i = 0; i < digits; i++) {
        ll p = rem * 10 + (str[i] - '0');
        rem = p % mod;
    }
}

int main(void) {
    ll num = 254;
    string str = "254";
    ll digits = str.size();
    ll rem1 = 0, rem2 = 0;
    integer_rem(num, rem1), str_rem(str, digit, rem2);
    cout << "rem1 = " << rem1 << ", rem2 = " << rem2 << '\n';
    return 0;
}

トレース

整数254をmod = 3で割ったときの剰余計算

// 整数254を数値型で表す場合（integer_rem）

num = 254
num % mod = rem1
254 % 3 = 2
rem1 = 2

// 整数254を文字列型で表す場合（str_rem）

i	str[i]	str[i] - '0'	p	rem2
0	'2'	2	2	2
1	'5'	5	25	1
2	'4'	4	14	2

※ str[i] - '0' ...char型（str[i]）をint型にキャスト
rem = 2

実行結果

rem1 = 2, rem2 = 2

関連問題

・AtCoder Beginner Contest 135 E - Digits Parade
・AtCoder Regular Contest 154 A - Swap Digit