[1,n]の逆元を列挙

inv_list.cpp

#include <iostream>
#include <vector>

using namespace std;

vector<int> make_inv_list(int n,int mod) {
    vector<int> inv_list(n+1);
    inv_list[1] = 1;

    for(int i=2;i<inv_list.size();i++) {
        inv_list[i] = (mod - mod/i) * inv_list[mod%i] % mod;
    }

    return inv_list;
}

int main() {
    vector<int> inv_list = make_inv_list(12,13);

    for(int i=1;i<inv_list.size();i++) {
        printf("%2d * %2d = %d\n",i,inv_list[i],i*inv_list[i]%13);
    }

        
    return 0;
}