巨大な数のmod (10000桁とか)

  • 別名、(数値)文字列のmodとも言えるかも
  • 10000桁などの数値はlong longなどでは受け取れない
    • 文字列で受け取るしかない
  • 1文字ずつ処理していけばいい
ll string_mod(string s, ll mod){
    ll rest = 0;
    for(char c : s){
        ll v = c-'0';
        rest = (rest*10 + v) % mod;
    }
    return rest;
}

この考えが必要な問題の例

動作確認Code

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

#define pn(s) cout << (#s) << " " << (s) << endl

ll string_mod(string s, ll mod){
    ll rest = 0;
    for(char c : s){
        ll v = c-'0';
        rest = (rest*10 + v) % mod;
    }
    return rest;
}

int main(){
    ll a = 5877462258937598;
    pn(a % 7);
    pn(a % 17);
    pn(a % 23);
    
    string s = to_string(a);
    pn(string_mod(s, 7));
    pn(string_mod(s, 17));
    pn(string_mod(s, 23));
    
    return 0;
}

出力

a % 7 0
a % 17 14
a % 23 22
string_mod(s, 7) 0
string_mod(s, 17) 14
string_mod(s, 23) 22