@[DoraYaoxy](/user/612567) $gcd(k,n)$ 拿线性筛递推，式子就是套个板，网上应该有
by char_cha_ch @ 2024-03-27 21:47:39
@[char_cha_ch](/user/701221) 这玩意能线性筛递推的？？
by DoraYaoxy @ 2024-03-27 21:50:26
@[DoraYaoxy](/user/612567) 就是你存下来它的最小因子和最小因子次数。
by char_cha_ch @ 2024-03-27 21:51:48
@[char_cha_ch](/user/701221) 抽象。
by Hot_tear @ 2024-03-27 21:54:10
@[char_cha_ch](/user/701221) 那有 $O(n \sqrt n)$ 出 $f(n)$ 前缀和的柿子吗。
by DoraYaoxy @ 2024-03-27 21:55:33
@[DoraYaoxy](/user/612567) gcd 的复杂度要比 $O(n\log n)$ 快，基本上可以看做 $O(kn)$ $k$ 为常数，而且 $f(n)$ 最小值例如 $f(5)$ 应当是 $-1+1+(-1)+1+(-5)$ 理论上只要可以取到负无穷，取一个极大的质数，那么最小值应当是无限小的，如错轻喷QAQ
by Hot_tear @ 2024-03-27 21:56:04
@[Hot_tear](/user/737112) 我去我是弱智。内什么循环只到 $n-1$。
by DoraYaoxy @ 2024-03-27 21:57:20
@[char_cha_ch](/user/701221) 有没有一种可能， exgcd 的复杂度是和 gcd 一样的？
by Hot_tear @ 2024-03-27 21:59:33
@[DoraYaoxy](/user/612567) $\sum_{d|n}\mu(d)\sum_{dg|n}(-1)^gg\sum_{i=1}^{\frac{n}{g}}(-1)^i$
by char_cha_ch @ 2024-03-27 22:09:10
@[DoraYaoxy](/user/612567) $\sum_{d|n}\mu(d)\sum_{t=1}^{\frac{n}{d}}(-1)^{td}td\sum_{i=1}^{\frac{n}{d}} (-1)^i$
by char_cha_ch @ 2024-03-27 22:12:44