Mod int

[cameroncuster]

so when we integrate with barrett division we should explain why and how much of a speed up contestants can expect, also document say exactly the range of numbers it works for (like you said)

[lrvideckis]

So regarding integrating with barrett division:

well there's 2 cases:

1. the mod is known at compile time: 1e9+7; NTT mod; For this, let's just have a global const MOD: u64 = ... and do the mod int in like in this PR; basically I don't think there's any performance gain with barrett here because % is now a bunch of shifts/adds I think
2. mod is not known at compile time: so this one is tricky: What I want is to have a single instance of the barrett struct; initialized right after reading in the mod from input. Then have all instances of the mod-int rely on this single instance of barrett.

one solution is to pass in the barrett struct to the constructor for each new instance of mod-int. I'm kinda against this, mostly because of the extra space. You could pass const reference of barrett to each mod int instance; but now you have to deal with lifetimes

Another solution is to have "global" mutable instance of the single barrett struct (basically a singleton); But rust makes this kind of thing hard/unclean, look at at-coder's impl of this

[lrvideckis]

My thought is; let's have the mod int only support compiler-time-known mods; (this is 95% of problems anyways); and for dynamic mod; we can just raw-dog it with barrett struct and no mod-int

[cameroncuster]

My thought is; let's have the mod int only support compiler-time-known mods; (this is 95% of problems anyways); and for dynamic mod; we can just raw-dog it with barrett struct and no mod-int

this is what a lot of libs do it seems

[lrvideckis]

how about this; let's merge the compiler time mod int for now

Later we can decide about how to do dynamic mod