ICPC 2023 miền Bắc - L: Euler

View as PDF
Submit solution
Points: 0.80
Time limit: 1.0s
Memory limit: 256M
Problem source:
ICPC 2023 miền Bắc
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

In case the statement didn't load correctly, you can download the statement here: Statement

Comments

Please read the guidelines before commenting.


  • 10
    KAKOII  commented on Oct. 8, 2023, 10:25 a.m. ← edit 17

    Hướng giải của mình:

    Để tính phi của tích 2 số ví dụ như ~\phi(ab)~ thì:

    Với ~d = \gcd(a, b)~

    Nếu ~d = 1~ thì: $$\phi(ab) = \phi(a) \cdot \phi(b)$$ Nếu ~d~ ~\neq~ ~1~ thì: $$\phi(ab) = \phi(a) \cdot \phi(b) \cdot \dfrac{d}{\phi(d)}$$ Từ đó, việc tính:

    $$ans = \sum_{i=1}^{b} \phi(ai) $$

    sẽ dễ hơn nhiều UwU