链接：https://ac.nowcoder.com/acm/contest/992/D
$a_{i}=\dfrac {3a_{i-1}-a_{i-2}}{2}+i+1$
移项再化一下
$a_{i}-a_{i-1}-2i=\dfrac {1}{2}\left[ a_{i-1}-a_{i-2}-2\left( i-1\right) \right]$
令$t_{i}=t_{i}=a_{i}-a_{i-1}-2i$
由于$a_{0}=0$ $a_{1}=2$ 所以$t_{1}=0$
所以$t_{i}=0$ $(i\geq 1)$
即$a_{i}=a_{i-1}+2i$
$\left\{\begin{matrix}
& a_{i}=a_{i-1}+2i& \\
& \cdots & \\
& a_{1}=a_{0}+2\times 1 &
\end{matrix}\right.$
$i$个式子相加得到
$S_{i}=S_{i-1}+i\left( i+1\right)$
所以$a_{i}=i^{2} + i$
也可以打表，但我感觉打表会不会更难看出来?
现在可以先把1~$n$的总和先求出来，再减去与$m$不互质的和就是答案了。
预处理出$m$的素因子，然后枚举一下所有组合的情况(由于$m$随机生成，素因子个数不会很多)
每一个素因子乘积的组合$k$有$\lfloor \dfrac {n}{k}\rfloor$个
然后容斥一下
$S_{n}=\dfrac {n\cdot \left( n+1\right) \left( 2n+1\right) }{6}$
$k^{2}+\left( 2k\right) ^{2}+\ldots +\left( \lfloor \dfrac {n}{k}\rfloor k\right) ^{2}$
把$k^{2}$提出来就又是一个平方和了
1~$i$的和同理
#include <bits/stdc++.h> #define ll long long using namespace std; const ll MOD = 1E9 + 7; const ll inv2 = 500000004; const ll inv6 = 166666668; ll n, m; ll fac[10000]; inline ll sqr(ll x) { return (x % MOD * (x + 1) % MOD * (2 * x + 1) % MOD * inv6) % MOD; } inline ll f(ll x) { return ((x + 1) * x % MOD * inv2 % MOD) % MOD; } inline ll cal(ll temp) { ll k = n / temp; return (sqr(k) * temp % MOD * temp % MOD + f(k) * temp % MOD) % MOD; } int main() { while (~scanf("%lld%lld", &n, &m)) { int cnt = 0; for (int i = 2; i * i <= m; i++) { if (m % i == 0) { fac[cnt++] = i; while (m % i == 0) m /= i; } } if (m != 1) fac[cnt++] = m; ll ans = cal(1); ll ans0 = 0; for (int i = 1; i < (1 << cnt); i++) { ll temp = 1; int sum = 0; for (int j = 0; j < cnt; j++) { if (i & (1 << j)) { sum++; temp *= fac[j]; } } if (sum & 1) { ans0 = (ans0 + cal(temp)) % MOD; } else { ans0 = (ans0 - cal(temp) + MOD) % MOD; } } ans = (ans - ans0 + MOD) % MOD; printf("%lld\n", ans); } return 0; }
吉首大学2019年程序设计竞赛（重现赛）D - 数列求和(嘤雄难度)
原文：https://www.cnblogs.com/Mrzdtz220/p/11188129.html
