## 前缀和 令 $f_i$ 表示答案为 $i$ 时候的方案数，求答案为 $i$ 的因数时的方案数。 ```cpp for (int i=1; i<=cnt; i++) for (int j=1; j<=n/p[i]; j++) f[j*p[i]]+=f[j]; ``` ## 后缀和 令 $f_i$ 表示答案为 $i$ 时候的方案数，求答案为 $i$ 的倍数时的方案数。 ```cpp for (int i=1; i<=cnt; i++) for (int j=n/p[i]; j>=1; j--) f[j]+=f[j*p[i]]; ``` ## 倒前缀和 令 $f_i$ 表示答案为 $i$ 因数时的方案数，求答案为 $i$ 时的方案数。 ```cpp for (int i=cnt; i>=1; i--) for (int j=n/p[i]; j>=1; j--) f[j*p[i]]=-f[j]; ``` ## 倒后缀和 令 $f_i$ 表示答案为 $i$ 倍数时的方案数，求答案为 $i$ 是的方案数。 ```cpp for (int i=cnt; i>=1; i--) for (int j=1; j<=n/p[i]; j++) f[j]-=f[j*p[i]]; ``` Loading... ## 前缀和 令 $f_i$ 表示答案为 $i$ 时候的方案数，求答案为 $i$ 的因数时的方案数。 ```cpp for (int i=1; i<=cnt; i++) for (int j=1; j<=n/p[i]; j++) f[j*p[i]]+=f[j]; ``` ## 后缀和 令 $f_i$ 表示答案为 $i$ 时候的方案数，求答案为 $i$ 的倍数时的方案数。 ```cpp for (int i=1; i<=cnt; i++) for (int j=n/p[i]; j>=1; j--) f[j]+=f[j*p[i]]; ``` ## 倒前缀和 令 $f_i$ 表示答案为 $i$ 因数时的方案数，求答案为 $i$ 时的方案数。 ```cpp for (int i=cnt; i>=1; i--) for (int j=n/p[i]; j>=1; j--) f[j*p[i]]=-f[j]; ``` ## 倒后缀和 令 $f_i$ 表示答案为 $i$ 倍数时的方案数，求答案为 $i$ 是的方案数。 ```cpp for (int i=cnt; i>=1; i--) for (int j=1; j<=n/p[i]; j++) f[j]-=f[j*p[i]]; ``` 最后修改：2025 年 07 月 02 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏