首页 > 代码库 > PE512
PE512
题意
$$f(n) = \sum_{i=1}^n {\phi (n^i)} (mod \ n+1)$$
$$g(n) = \sum_{i=1}^n {f(i)}$$
Find $g(5 \times 10^8) = ?$
解法:
如果有 $n = p_1^{t_1} p_2^{t_2}... p_m^{t_m}$
从而 $\phi (n) = n (1 - \frac{1}{p_1}) (1 - \frac{1}{p_2})... (1 - \frac{1}{p_m})$
取$n‘ = n^i$
从而 $\phi(n^i) = n^{i-1} \phi(n)$
$$f(n) = (1 + n + n^2 + ... + n^{n-1}) (mod \ n+1) \phi (n)$$
$$f(n) = (1+n)(1+n^2+...+n^{i-2}) + [n\ is\ an\ odd] (mod \ n+1) \phi(n)$$
从而
$$g(n) = \sum_{1 \leq k \leq n, k\ is\ an\ odd}{\phi(k)}$$
用杜教筛。
PE512
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。