615D - Множители

The way to solve this problem is easy. Just let $$$n=p_1^{c_1}p_2^{c_2}\cdots p_k^{c_k}$$$ ($$$p_i$$$ are pairwise different) then the answer will be

There're more than one way to get ans (a simple way is to use prefix product). But today I read a solution which I could not understand:

My only question: why we can keep the factor 2 by mod 2*(mod-1)? Thanks in advance

Some properties of bitwise operations seem very classical, but I had no idea of them until the first time I met them. Here are some examples: (^ is for bitwose XOR)

a+b = a&b + a|b

if a^b^c = 0, then (a-k)^(b-k)^(c-k)!=0 forall 0<k<=min(a,b,c)

a^b >= a-b (got it from uva12716 GCD XOR)

a+b = (a^b) + 2(a&b) (1451E1 - Битовые запросы (упрощенная версия))

There are countless blogs discussing the most basic properties like "a=b^c and b=a^c implies c=a^b", or tricks like "enumerate subsets with bitwise operations" and "swap two values without a third variable". But I didn't find what I need.

Can you give me a list of these special properties of bitwise operations? Or tell me that there's no need to know about them, everyone just derive them through the basic ones in a contest.

I was taught not to write things like a=a+++++a.

However I love writing a++ because I believe that it always gets executed after a whole sentence (perhaps, right after a , or ;?)

But today I wrote this and got WA:

if(hh < tt && a[hh+1] == a[hh]-1) c[hh+1] += 2*c[hh++];

wa code: 154812779

rewrote it like this and got AC:

if(hh < tt && a[hh+1] == a[hh]-1) c[hh+1] += 2*c[hh], hh++;

ac code: 154812722

I'm wondering if it's wrong somewhere else or am I misunderstanding the usage of x++?

I've always believed that getting the inverse of some integer n this way takes O(log(p)) time:

long long inv(long long n, long long p) {
	if (n == 1) return 1;
	return inv(p%n, p) * (p - p/n) % p;
}

But recently someone told me that it might be O(sqrt(p)).

So what is the correct time complexity?