Hỏi cách tính hàm Euler với số lớn

toidihoc · August 11, 2023, 2:54pm

Đề bài là như sau

Rõ ràng phi(a*b) >= phi(a) * phi(b) nên để phi lớn nhất thì cần tính phi(tích tất cả các data set), nên bài toán quy về tính phi của một số rất lớn, có thể lên đến (10^6)^{10^5} theo mod 1e9 + 7.

E đã biết một số tính chất của hàm phi như cách tính phi(n) = n*\prod_{i} \left(1-\dfrac{1}{p[i]}\right) (các p[i] là các ước nguyên tố của n), hoặc là nhân tính phi(a*b) = phi(a)*phi(b) nếu gcd(a,b) = 1, nhưng chưa thấy giúp ích được gì bài này ạ.

noname00 · August 11, 2023, 2:57pm

Bạn tự sinh trước danh sách các số nguyên tố không quá 1e6 (có tất cả 78948 số) bằng sàng nguyên tố.

Chỉ cần cải tiến code sàng nguyên tố một chút, thay vì state[i] lưu trạng thái số i là số nguyên tố hay không thì lưu ước nguyên tố nhỏ nhất của i.

rogp10 · September 1, 2023, 4:06am

Bài này gồm 2 phần là phân tích TSNT của tối đa 10^5 số, cộng gộp số mũ (thực hiện phép nhân) của chúng và tính biểu thức vừa sinh ra đó. ~~Phép chia mod là khả dĩ vì 10^9+7 nguyên tố~~ (nhầm qua công thức tính tổng ước rồi ) Khi đặt sieve[i] = ước nguyên tố bé nhất của i thì có thê truy được đến sieve[i/sieve[i]], dần dần thu được phân tích TSNT của số ban đầu. Vì vậy có thể phân tích TSNT hàng loạt.

tntxtnt · August 12, 2023, 3:08am

đâu cần tìm ước nguyên tố bé nhất đâu nhỉ tìm ước nguyên tố được rồi:

Ví dụ Chạy “sàng” tìm ước nguyên tố của từng số < 100:

Ban đầu `prime_div` =

\begin{array}{ccccccccccc} & \textcolor{gray}{0} & \textcolor{gray}{1} & \textcolor{gray}{2} & \textcolor{gray}{3} & \textcolor{gray}{4} & \textcolor{gray}{5} & \textcolor{gray}{6} & \textcolor{gray}{7} & \textcolor{gray}{8} & \textcolor{gray}{9} & \\ \textcolor{gray}{0} & \textcolor{red}{ 0} & \textcolor{red}{ 1} & \textcolor{red}{ 2} & \textcolor{red}{ 3} & \textcolor{red}{ 4} & \textcolor{red}{ 5} & \textcolor{red}{ 6} & \textcolor{red}{ 7} & \textcolor{red}{ 8} & \textcolor{red}{ 9} & \\ \textcolor{gray}{1} & \textcolor{red}{10} & \textcolor{red}{11} & \textcolor{red}{12} & \textcolor{red}{13} & \textcolor{red}{14} & \textcolor{red}{15} & \textcolor{red}{16} & \textcolor{red}{17} & \textcolor{red}{18} & \textcolor{red}{19} & \\ \textcolor{gray}{2} & \textcolor{red}{20} & \textcolor{red}{21} & \textcolor{red}{22} & \textcolor{red}{23} & \textcolor{red}{24} & \textcolor{red}{25} & \textcolor{red}{26} & \textcolor{red}{27} & \textcolor{red}{28} & \textcolor{red}{29} & \\ \textcolor{gray}{3} & \textcolor{red}{30} & \textcolor{red}{31} & \textcolor{red}{32} & \textcolor{red}{33} & \textcolor{red}{34} & \textcolor{red}{35} & \textcolor{red}{36} & \textcolor{red}{37} & \textcolor{red}{38} & \textcolor{red}{39} & \\ \textcolor{gray}{4} & \textcolor{red}{40} & \textcolor{red}{41} & \textcolor{red}{42} & \textcolor{red}{43} & \textcolor{red}{44} & \textcolor{red}{45} & \textcolor{red}{46} & \textcolor{red}{47} & \textcolor{red}{48} & \textcolor{red}{49} & \\ \textcolor{gray}{5} & \textcolor{red}{50} & \textcolor{red}{51} & \textcolor{red}{52} & \textcolor{red}{53} & \textcolor{red}{54} & \textcolor{red}{55} & \textcolor{red}{56} & \textcolor{red}{57} & \textcolor{red}{58} & \textcolor{red}{59} & \\ \textcolor{gray}{6} & \textcolor{red}{60} & \textcolor{red}{61} & \textcolor{red}{62} & \textcolor{red}{63} & \textcolor{red}{64} & \textcolor{red}{65} & \textcolor{red}{66} & \textcolor{red}{67} & \textcolor{red}{68} & \textcolor{red}{69} & \\ \textcolor{gray}{7} & \textcolor{red}{70} & \textcolor{red}{71} & \textcolor{red}{72} & \textcolor{red}{73} & \textcolor{red}{74} & \textcolor{red}{75} & \textcolor{red}{76} & \textcolor{red}{77} & \textcolor{red}{78} & \textcolor{red}{79} & \\ \textcolor{gray}{8} & \textcolor{red}{80} & \textcolor{red}{81} & \textcolor{red}{82} & \textcolor{red}{83} & \textcolor{red}{84} & \textcolor{red}{85} & \textcolor{red}{86} & \textcolor{red}{87} & \textcolor{red}{88} & \textcolor{red}{89} & \\ \textcolor{gray}{9} & \textcolor{red}{90} & \textcolor{red}{91} & \textcolor{red}{92} & \textcolor{red}{93} & \textcolor{red}{94} & \textcolor{red}{95} & \textcolor{red}{96} & \textcolor{red}{97} & \textcolor{red}{98} & \textcolor{red}{99} & \\ \end{array}

n = 2:

\begin{array}{ccccccccccc} & \textcolor{gray}{0} & \textcolor{gray}{1} & \textcolor{gray}{2} & \textcolor{gray}{3} & \textcolor{gray}{4} & \textcolor{gray}{5} & \textcolor{gray}{6} & \textcolor{gray}{7} & \textcolor{gray}{8} & \textcolor{gray}{9} & \\ \textcolor{gray}{0} & 0 & 1 & 2 & 3 & \textcolor{red}{ 2} & 5 & \textcolor{red}{ 2} & 7 & \textcolor{red}{ 2} & 9 & \\ \textcolor{gray}{1} & \textcolor{red}{ 2} & 11 & \textcolor{red}{ 2} & 13 & \textcolor{red}{ 2} & 15 & \textcolor{red}{ 2} & 17 & \textcolor{red}{ 2} & 19 & \\ \textcolor{gray}{2} & \textcolor{red}{ 2} & 21 & \textcolor{red}{ 2} & 23 & \textcolor{red}{ 2} & 25 & \textcolor{red}{ 2} & 27 & \textcolor{red}{ 2} & 29 & \\ \textcolor{gray}{3} & \textcolor{red}{ 2} & 31 & \textcolor{red}{ 2} & 33 & \textcolor{red}{ 2} & 35 & \textcolor{red}{ 2} & 37 & \textcolor{red}{ 2} & 39 & \\ \textcolor{gray}{4} & \textcolor{red}{ 2} & 41 & \textcolor{red}{ 2} & 43 & \textcolor{red}{ 2} & 45 & \textcolor{red}{ 2} & 47 & \textcolor{red}{ 2} & 49 & \\ \textcolor{gray}{5} & \textcolor{red}{ 2} & 51 & \textcolor{red}{ 2} & 53 & \textcolor{red}{ 2} & 55 & \textcolor{red}{ 2} & 57 & \textcolor{red}{ 2} & 59 & \\ \textcolor{gray}{6} & \textcolor{red}{ 2} & 61 & \textcolor{red}{ 2} & 63 & \textcolor{red}{ 2} & 65 & \textcolor{red}{ 2} & 67 & \textcolor{red}{ 2} & 69 & \\ \textcolor{gray}{7} & \textcolor{red}{ 2} & 71 & \textcolor{red}{ 2} & 73 & \textcolor{red}{ 2} & 75 & \textcolor{red}{ 2} & 77 & \textcolor{red}{ 2} & 79 & \\ \textcolor{gray}{8} & \textcolor{red}{ 2} & 81 & \textcolor{red}{ 2} & 83 & \textcolor{red}{ 2} & 85 & \textcolor{red}{ 2} & 87 & \textcolor{red}{ 2} & 89 & \\ \textcolor{gray}{9} & \textcolor{red}{ 2} & 91 & \textcolor{red}{ 2} & 93 & \textcolor{red}{ 2} & 95 & \textcolor{red}{ 2} & 97 & \textcolor{red}{ 2} & 99 & \\ \end{array}

n = 3:

\begin{array}{ccccccccccc} & \textcolor{gray}{0} & \textcolor{gray}{1} & \textcolor{gray}{2} & \textcolor{gray}{3} & \textcolor{gray}{4} & \textcolor{gray}{5} & \textcolor{gray}{6} & \textcolor{gray}{7} & \textcolor{gray}{8} & \textcolor{gray}{9} & \\ \textcolor{gray}{0} & 0 & 1 & 2 & 3 & 2 & 5 & 2 & 7 & 2 & \textcolor{red}{ 3} & \\ \textcolor{gray}{1} & 2 & 11 & \textcolor{red}{ 3} & 13 & 2 & \textcolor{red}{ 3} & 2 & 17 & \textcolor{red}{ 3} & 19 & \\ \textcolor{gray}{2} & 2 & \textcolor{red}{ 3} & 2 & 23 & \textcolor{red}{ 3} & 25 & 2 & \textcolor{red}{ 3} & 2 & 29 & \\ \textcolor{gray}{3} & \textcolor{red}{ 3} & 31 & 2 & \textcolor{red}{ 3} & 2 & 35 & \textcolor{red}{ 3} & 37 & 2 & \textcolor{red}{ 3} & \\ \textcolor{gray}{4} & 2 & 41 & \textcolor{red}{ 3} & 43 & 2 & \textcolor{red}{ 3} & 2 & 47 & \textcolor{red}{ 3} & 49 & \\ \textcolor{gray}{5} & 2 & \textcolor{red}{ 3} & 2 & 53 & \textcolor{red}{ 3} & 55 & 2 & \textcolor{red}{ 3} & 2 & 59 & \\ \textcolor{gray}{6} & \textcolor{red}{ 3} & 61 & 2 & \textcolor{red}{ 3} & 2 & 65 & \textcolor{red}{ 3} & 67 & 2 & \textcolor{red}{ 3} & \\ \textcolor{gray}{7} & 2 & 71 & \textcolor{red}{ 3} & 73 & 2 & \textcolor{red}{ 3} & 2 & 77 & \textcolor{red}{ 3} & 79 & \\ \textcolor{gray}{8} & 2 & \textcolor{red}{ 3} & 2 & 83 & \textcolor{red}{ 3} & 85 & 2 & \textcolor{red}{ 3} & 2 & 89 & \\ \textcolor{gray}{9} & \textcolor{red}{ 3} & 91 & 2 & \textcolor{red}{ 3} & 2 & 95 & \textcolor{red}{ 3} & 97 & 2 & \textcolor{red}{ 3} & \\ \end{array}

n = 4:

prime_div[4] = 2 != 4 vậy 4 không nguyên tố, bỏ qua

n = 5:

\begin{array}{ccccccccccc} & \textcolor{gray}{0} & \textcolor{gray}{1} & \textcolor{gray}{2} & \textcolor{gray}{3} & \textcolor{gray}{4} & \textcolor{gray}{5} & \textcolor{gray}{6} & \textcolor{gray}{7} & \textcolor{gray}{8} & \textcolor{gray}{9} & \\ \textcolor{gray}{0} & 0 & 1 & 2 & 3 & 2 & 5 & 2 & 7 & 2 & 3 & \\ \textcolor{gray}{1} & 2 & 11 & 3 & 13 & 2 & 3 & 2 & 17 & 3 & 19 & \\ \textcolor{gray}{2} & 2 & 3 & 2 & 23 & 3 & \textcolor{red}{ 5} & 2 & 3 & 2 & 29 & \\ \textcolor{gray}{3} & \textcolor{red}{ 5} & 31 & 2 & 3 & 2 & \textcolor{red}{ 5} & 3 & 37 & 2 & 3 & \\ \textcolor{gray}{4} & \textcolor{red}{ 5} & 41 & 3 & 43 & 2 & \textcolor{red}{ 5} & 2 & 47 & 3 & 49 & \\ \textcolor{gray}{5} & \textcolor{red}{ 5} & 3 & 2 & 53 & 3 & \textcolor{red}{ 5} & 2 & 3 & 2 & 59 & \\ \textcolor{gray}{6} & \textcolor{red}{ 5} & 61 & 2 & 3 & 2 & \textcolor{red}{ 5} & 3 & 67 & 2 & 3 & \\ \textcolor{gray}{7} & \textcolor{red}{ 5} & 71 & 3 & 73 & 2 & \textcolor{red}{ 5} & 2 & 77 & 3 & 79 & \\ \textcolor{gray}{8} & \textcolor{red}{ 5} & 3 & 2 & 83 & 3 & \textcolor{red}{ 5} & 2 & 3 & 2 & 89 & \\ \textcolor{gray}{9} & \textcolor{red}{ 5} & 91 & 2 & 3 & 2 & \textcolor{red}{ 5} & 3 & 97 & 2 & 3 & \\ \end{array}

n = 6:

prime_div[6] = 2 != 6 vậy 6 không nguyên tố, bỏ qua

n = 7:

\begin{array}{ccccccccccc} & \textcolor{gray}{0} & \textcolor{gray}{1} & \textcolor{gray}{2} & \textcolor{gray}{3} & \textcolor{gray}{4} & \textcolor{gray}{5} & \textcolor{gray}{6} & \textcolor{gray}{7} & \textcolor{gray}{8} & \textcolor{gray}{9} & \\ \textcolor{gray}{0} & 0 & 1 & 2 & 3 & 2 & 5 & 2 & 7 & 2 & 3 & \\ \textcolor{gray}{1} & 2 & 11 & 3 & 13 & 2 & 3 & 2 & 17 & 3 & 19 & \\ \textcolor{gray}{2} & 2 & 3 & 2 & 23 & 3 & 5 & 2 & 3 & 2 & 29 & \\ \textcolor{gray}{3} & 5 & 31 & 2 & 3 & 2 & 5 & 3 & 37 & 2 & 3 & \\ \textcolor{gray}{4} & 5 & 41 & 3 & 43 & 2 & 5 & 2 & 47 & 3 & \textcolor{red}{ 7} & \\ \textcolor{gray}{5} & 5 & 3 & 2 & 53 & 3 & 5 & \textcolor{red}{ 7} & 3 & 2 & 59 & \\ \textcolor{gray}{6} & 5 & 61 & 2 & \textcolor{red}{ 7} & 2 & 5 & 3 & 67 & 2 & 3 & \\ \textcolor{gray}{7} & \textcolor{red}{ 7} & 71 & 3 & 73 & 2 & 5 & 2 & \textcolor{red}{ 7} & 3 & 79 & \\ \textcolor{gray}{8} & 5 & 3 & 2 & 83 & \textcolor{red}{ 7} & 5 & 2 & 3 & 2 & 89 & \\ \textcolor{gray}{9} & 5 & \textcolor{red}{ 7} & 2 & 3 & 2 & 5 & 3 & 97 & \textcolor{red}{ 7} & 3 & \\ \end{array}

n = 8:

prime_div[8] = 2 != 8 vậy 8 không nguyên tố, bỏ qua

n = 9:

prime_div[9] = 3 != 9 vậy 9 không nguyên tố, bỏ qua

Chỉ chạy tới \left\lfloor{\sqrt{99}}\right\rfloor = 9, vậy mảng prime_div cuối cùng là

\begin{array}{ccccccccccc} & \textcolor{gray}{0} & \textcolor{gray}{1} & \textcolor{gray}{2} & \textcolor{gray}{3} & \textcolor{gray}{4} & \textcolor{gray}{5} & \textcolor{gray}{6} & \textcolor{gray}{7} & \textcolor{gray}{8} & \textcolor{gray}{9} & \\ \textcolor{gray}{0} & 0 & 1 & \textcolor{green}{ 2} & \textcolor{green}{ 3} & 2 & \textcolor{green}{ 5} & 2 & \textcolor{green}{ 7} & 2 & 3 & \\ \textcolor{gray}{1} & 2 & \textcolor{green}{11} & 3 & \textcolor{green}{13} & 2 & 3 & 2 & \textcolor{green}{17} & 3 & \textcolor{green}{19} & \\ \textcolor{gray}{2} & 2 & 3 & 2 & \textcolor{green}{23} & 3 & 5 & 2 & 3 & 2 & \textcolor{green}{29} & \\ \textcolor{gray}{3} & 5 & \textcolor{green}{31} & 2 & 3 & 2 & 5 & 3 & \textcolor{green}{37} & 2 & 3 & \\ \textcolor{gray}{4} & 5 & \textcolor{green}{41} & 3 & \textcolor{green}{43} & 2 & 5 & 2 & \textcolor{green}{47} & 3 & 7 & \\ \textcolor{gray}{5} & 5 & 3 & 2 & \textcolor{green}{53} & 3 & 5 & 7 & 3 & 2 & \textcolor{green}{59} & \\ \textcolor{gray}{6} & 5 & \textcolor{green}{61} & 2 & 7 & 2 & 5 & 3 & \textcolor{green}{67} & 2 & 3 & \\ \textcolor{gray}{7} & 7 & \textcolor{green}{71} & 3 & \textcolor{green}{73} & 2 & 5 & 2 & 7 & 3 & \textcolor{green}{79} & \\ \textcolor{gray}{8} & 5 & 3 & 2 & \textcolor{green}{83} & 7 & 5 & 2 & 3 & 2 & \textcolor{green}{89} & \\ \textcolor{gray}{9} & 5 & 7 & 2 & 3 & 2 & 5 & 3 & \textcolor{green}{97} & 7 & 3 & \\ \end{array}

mấy số nt được highlight = màu xanh lá là những số có prime divisor = chính nó (trừ 0, 1)

ko cần tìm min divisor cũng được, ví dụ 70 tìm 1 ước nt là 7 là được rồi :V Tách 70 thành thừa số nt thì chạy 70 --> 7 xuống 70/7 = 10 tìm tiếp, 10 --> 2 chạy xuống 10/2 = 5 tìm tiếp, 5 --> 5 là số nt nên dừng, vậy các ước nt của 70 là 7, 2, 5. Tìm min divisor thì khi phân tích 1 số ra thừa số nt xài bảng này thì thừa số nt nó sắp xếp từ nhỏ tới lớn mà bài này ko bắt buộc :V
vd khác 45 -> 5, 9 -> 3, 3 -> 3 vậy 45 có thừa số nt là 5, 3, 3

Tìm được cái bảng kia rồi thì ví dụ tìm \phi(70 * 45) thì mò ra lẹ là \phi(70 * 45) = \phi(7 * 2 * 5 * 5 * 3 * 3) = \phi(7^1 * 2^1 * 5^2 * 3^2) = 7^0(7 - 1)2^0(2 - 1)5^1(5 - 1)3^1(3-1) = 1*6*1*1*5*4*3*2 = 720

Gọi N là kích thước mảng, V là giá trị lớn nhất trong bảng thì ta có:

Bước tìm ước nguyên tố của V số từ 1 tới V tốn O(V\log{\log{V}})
Mỗi lần tách 1 số < V thành thừa số nt thì tốn O(\log{V}) vì số lượng ước số của 1 số <= log cơ số 2 của số đó. Tách được 1 ước nt rồi bỏ vào cái hash map thì tốn O(1), O(\log{V} thừa số nt vẫn chỉ tốn O(\log{V}). Vậy làm với N số thì đpt là O(N\log{V})
Bước nhân các thừa số nt trong hash map kia lại ra kết quả thì tốn O(1) mỗi phép nhân, mà có X phép nhân tổng cộng với X = size của cái hash map, mà X này tối đa = số lượng các số nt <= V, vậy nó là O(V / \log{V})

Vậy đpt tổng cộng là O\left(V\log{\log{V}} + N\log{V} + \dfrac{V}{\log{V}}\right)
hay O(V\log{\log{V}} + N\log{V})
V cỡ 1e6, N cỡ 1e5 thì tốn cỡ 5e6 + 2e6 ~ 7e6 ops chắc chạy dưới 1s được :V :V

tntxtnt · August 12, 2023, 3:29pm

sai chỗ này nè base là int, mà ở đây base có thể lên tới 1e9. Sửa lẹ kiểu base thành long long là được

toidihoc · August 12, 2023, 3:56pm

cảm ơn bạn nhiều được thêm vài điểm rồi nhưng lại dính run time error ở test case khác, căng thật

tntxtnt · August 12, 2023, 4:19pm

chạy đúng à đừng chôm code của toy sửa lại code trên đi để toy xóa

noname00 · August 12, 2023, 4:48pm

Limit đề cho là xét các số đến 10^6 mà set N = 10^5 thì runtime error là đúng rồi bạn.

noname00 · August 13, 2023, 11:27am

A post was split to a new topic: Những bài tập về thuật toán tính toán có cần thiết để đi làm không?

toidihoc · August 14, 2023, 3:54pm

chạy đúng nhưng mà e vẫn đang sửa code lại chứ ko lấy code của a rồi submit xong để đấy đâu ạ:D mỗi lần sửa ăn được thêm vài điểm là thấy mừng rồi ấy chứ
… tạm thời vẫn chưa AC …

toidihoc · August 14, 2023, 4:01pm

à đúng rồi ạ T.T sai ngớ ngẩn quá, cảm ơn anh nhiều ạ