HDU 6706 – huntian oy

题目链接:HDU 6706

$$ {\rm gcd}(i,j)=1, i > j \rightarrow {\rm gcd}(i^a – j^a, i^b – j^b) = i^{{\rm gcd}(a,b)} – j^{{\rm gcd}(a,b)} $$

$$ \begin{aligned} f(n, a, b) = & \sum_{i = 1}^{n} \sum_{j = 1}^{i} {\rm gcd}(i^a – j^a, i^b – j^b)[{\rm gcd}(i,j)=1] \\ = & \sum_{i = 1}^{n} \sum_{j=1}^{i} (i-j)[{\rm gcd}(i, j)=1] \\ = & \sum_{i = 1}^{n} \sum_{j = 1}^{i} i [{\rm gcd}(i, j) = 1] – \sum_{i = 1}^{n} \sum_{j = 1}^{i} j[{\rm gcd}(i, j) = 1]  \end{aligned} $$

被减数$\sum_{i = 1}^{n} \sum_{j=1}^{i} = \sum_{i = 1}^{n} i \sum_{j = 1}^{i} [{\rm gcd}(i,j) = 1] = \sum_{i = 1}^{n} i \varphi(i) $。

减数考虑${\rm gcd}(i,j) = {\rm gcd}(i, i – j)$,故如果存在一个有贡献的$j’$,一定存在一个有贡献的$i – j’$,他们的贡献和是$i$。对于每一个这样的$(i)$都有$\varphi(i)$组$(i,j)$,去重之后可以表示为$\sum_{i = 1}^{n} (\frac{i \varphi(i)}{2} + [i=1])$。

所以我们可以推得:

$$f(n, a, b) = \frac{\sum_{i = 1}^{n} i \varphi(i) – 1}{2}$$

$f(x) = x \varphi(x)$是积性函数,考虑使用筛法。设$g(x) = x$,令$f$和$g$做Direclet卷积:

$$ f * g (x) = \sum_{d|x} \frac{x}{d} \varphi(\frac{x}{d}) d = \sum_{d|n} x \varphi(\frac{x}{d}) = x \sum_{d|n} \varphi(\frac{x}{d}) = x^2  $$

可求前缀和,记$\sum_{x=1}^{n} f(x) = F(n)$,也就是我们要求的值,那么

$$ \begin{aligned} \frac{n(n+1)(2n + 1)}{6} = \sum_{x = 1}^{n} f * g(x) =&  \sum_{x = 1}^{n} \sum_{d|x} x \varphi(\frac{x}{d}) \\ = & \sum_{d=1}^{n}\sum_{x=1}^{n} x \varphi(\frac{x}{d}) [d | x] \\ = & \sum_{d=1}^{n}  \sum_{x = 1}^{\lfloor \frac{n}{d} \rfloor} xd\varphi(x) \\ = & \sum_{d=1}^{n} d \sum_{x = 1}^{\lfloor \frac{n}{d} \rfloor} x \varphi(x) \\ = & F(n) + \sum_{d = 2}^{n} d F(\lfloor \frac{n}{d} \rfloor) \end{aligned} $$

所以我们可以得到

$$F(n) = \frac{n(n+1)(2n + 1)}{6} -\sum_{d = 2}^{n} d F(\lfloor \frac{n}{d} \rfloor)  $$

杜教筛即可。

实测结果预处理前$n \leq 3.5 \times 10^6$的$F(n)$是最快的,在HDU的老爷机上跑了998 MS。

预处理线性筛,对于积性函数$f(x) = x \varphi(x)$

  • $f(p) = p(p – 1)$
  • $f(p^k) = p^k \varphi(p^k)$,$f(p^{k+1}) = p^{k+1} \varphi(p^{k+1}) = p^{k+1} \varphi(p^k) p = p^{k+2} \varphi(p^k)$,所以$f(p^{k+1}) = p^2 f(p^k)$

 

 

2
说点什么

avatar
50
1 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
YuweiZhao0xfaner Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
0xfaner
游客
0xfaner

怎么你们都会杜教筛啊(