How do you express 2. condition with 2-sat clauses?

Newton's method has a quadratic convergence rate which means that the number of accurate digits doubles with every iteration. This implies that for N-bit integers this method requires around log(N) iterations. Obviously std::sqrt might be even faster.

When you apply for scholarships, there are often more points for international olympiad than national olympiad. Sometimes those are restricted only to IOI, but not always. So it might lead to discriminatory/unfair/unequal situation, but it probably affects only life of a few. It's quite complex topic and it's rather hard to evaluate it properly without doing research, statistical analysis etc. Also the effects may vary in different countries.

Hint: use segment tree to speed up computation of your dp (maybe more than one).

Um_nik wrote an entire blog dedicated to explaining how to practice Competitive Programming in a smart, effective way. I guess you should read it https://codeforces.com/blog/entry/98806

International Grandmaster doesn't know such a basic stuff. Kinda sus

Honestly, I don't think that's an issue. Isn't correct and efficient implementation part of solving the task? You may claim that it's unfair, because many people with brilliant ideas are limited by their knowledge of programming, but in the end of the day it is competitive programming. Ability to optimize the code and squeeze it into the time limit is valuable skill that should be rewarded. Otherwise we shouldn't call it "competitive programming", but "algorithmic problem solving" or something like that.

Seems like in the first code inner loop wasn't vectorized. Honestly, I wasn't sure if it would be so I used another variable to store maximum and turns out it was good decision xD

I've read something like https://www.archer.ac.uk/training/course-material/2017/10/KNL_Camb/Slides/L04-Vectorisation.pdf to learn about vectorization and pragmas. Maybe this will help you too

Consider two numbers a and b. If both of them have highest bit on the same position, then a&b > a^b. Otherwise a&b < a^b. The rest should be easy (if not, i can explain).

FYI after every contest someone complains about it, so you're not the first person, who thought about it. It's really annoying to read posts like this over and over, especially if you don't suggest any solution. Also just because you are bad, it doesn't mean that others are. E.g. yarek had rating of 2108 after first 3 contests, which, I believe, was International Master back then.

We can reduce the problem to couting the number of numbers relatively prime to m on interval [0..m/gcd(a, m)]. Let's say that m = m/gcd(a, m). Firstly you need to factorise m and store vector of unique prime factors. Then you can use the principle of inclusion and exclusion to calculate the number of such numbers that have common prime divisor with m.

You can use segment tree with operations: add 1 in point, find nth element. It's quite simple to find nth element. You just run from node v = 1 in tree and check whether the sum of subtree of left son is bigger than n. If it is then you look for (n-sum[left_son])th element in subtree of rightson. Otherwise you look for nth element in subtree of leftson.