You should resubmit!

Miller Rabin worked for me, in 0.3 seconds. Checked against 2,3,5,7,11. (should be enough).

EDIT: Sorry, I forgot to mention that I used __int128

Hint: slow part of your solution is doing (A*B)%C with binary multiplication. If you are going to use it — it will be not so easy to make it work within TL :)

There are several ways to make it work faster; for me following fix sounds simplest:

long long mult(long long a, long long b, long long mod)
{
	__int128 res = a;
	res *= b;
	res %= mod;
	a = res;
	return a;
}

Miller Rabin was the intended solution. In my solution, which you can find under setter's solution, I used the deterministic version, but random one will work also.

Outlines of solutions and my codes to all problems are already in system, so they should be posted soon (it seems like some of them are available already). Feel free to ask questions if something isn't clear or if you need more detailed explanation of some parts.

There was a small hint about approximate problem — in announcement I told you to not be afraid of it :) It's not actually a standard approximate problem — obviously you can try some optimizations and stuff like that, but for this task exact solution (giving zero penalty) exists and it is not hard to find — you have to pick vertices of some regular tetrahedron, defined by center and edge length :) You can either derive required formulas by yourself or find them in Wikipedia :) I believe there would be much more AC's on this one in case it wasn't an approximate problem and it was put somewhere in the middle of the problemset. And it was another try to make people not afraid of approximate problems and/or scary/complicated problem statements.

O(2^n2 * n1) for every case! Greedy + Bitmask

Capacities of bottles of Amulus form a sequence called superincreasing sequence (you can google for it), for which a problem of deciding if any subset of them sum up to a certain value can be solved greedily in linear time. Check the editorial by Bohdan for more details and his or mine solution in setter/tester solution section.

I used mobius inversion to solve the first one, second and third were simple modifications of the first one!

In superfunctions I used a very nice, but not well know result (the paper with it is given in the editorial). However, if you examine the nature of these functions and group the terms in a different order of summation, you should get the result also. Editorial explains this also.

How the second formula follows from the first fact, please?