Pillai’s arithmetical function – Thuật toán tính hàm Pillai

Trong lý thuyết số, hàm số Pillai được định nghĩa theo công thức sau:

P(n)=\sum_{k=1}^n\gcd(k,n)

Ta có thể viết lại như sau:
P(n) = \sum_{d\mid n} d cnt(d), với d là ước số của n và cnt(d) là số gặp (i,n) thoả mãn gcd(i,n) = d.

Theo tính chất của hàm gcd, nếu ta có gcd(a,b) = d thì gcd(a/d, b/d) = 1. Do đó công thức của hàm Pillai sẽ là:
P(n) = \sum_{d\mid n} d \phi(n/d), với \phiHàm phi Euler

Có thể tính được giá trị hàm Pillai của các số trong khoảng [1..N] bằng cách sàng Sieve tính trước Phi hàm Euler, sau đó sàng thêm một lần nữa để tính P(n).
Code
Độ phức tạp O(NlogN)

Nguồn tham khảo:

[1] https://en.wikipedia.org/wiki/Pillai’s_arithmetical_function

Happy coding

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s