### Pranayhalo's blog

By Pranayhalo, history, 4 years ago,

I am trying to solve Coprime Integers. I believe the central idea to the problem involves the ETF, as I can solve the number of integers between a <= x <= b such that gcd(x, n) = 1, and loop this (or possibly leverage Euler Phi Function) for all c <= n <= d. If anyone has a general explanation of the solution, this would also be helpful.

Nevertheless, ETF is "the number of integers [1...n] that are coprime with n. I need "the number of integers [1...c] that are coprime with n.

For example, if n=40=2^3*5 and c=12, then the following 5 pairs are valid: (1,40), (3,40), (7,40), (9,40), (11,40). I think the way this should be generated is this: total number of integers — number of integers not coprime + the number of double counts= 12 — floor(12/2) — floor(12/5) + floor(12/10) = 5. However, this is too inefficient as inclusion-exclusion may take a long time.

I know that the ETF is multiplicative and that phi(P1^x * P2^y) = phi(P1^x) * phi(P2^y). However, this calculates the first ETF definition given above, not the second type which is what I need. How can I transform this to work for my need? And what is the reason behind it? My math is not super strong, so details would be helpful!

• +4

By Pranayhalo, history, 4 years ago,

Wondering if there are any good resources (or editorials) to aid when trying to upsolve regional ACM-ICPC contests. I see they have coded solutions, but without some editorial, I am not able to fully understand why what works. I am specifically asking for the Mid-Central PC 2018. If not, would anyone be able to help me in solving the following problem from MCPC18 K: Repeated Substrings? Thanks!

• +6

By Pranayhalo, history, 4 years ago,

I am attempting to make my debugging tool better for C++. I currently have a script that runs with the following flags: -Wall -Wextra -O2 -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC. When I run my code with these flags, one of the errors I sometimes receive is that I attempted to a subscript container with an out-of-bounds index. While this is very useful, if my code is long, I am not sure which line and/or container this refers to. Is there any way to make this more specific (like how Java IDE tells the specific line and object that caused the error).

The following is an example:

Error: attempt to subscript container with out-of-bounds index 8, but
container only holds 8 elements.

Objects involved in the operation:
sequence "this" @ 0x0061FE40 {
type = std::__debug::vector<int, std::allocator<int> >;
}
• +3