吉首大学2019年程序设计竞赛（重现赛）D

链接：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 + ;

const ll inv2 = ;

const ll inv6 = ;

ll n, m;

ll fac[];

inline ll sqr(ll x) {

    return (x % MOD * (x + ) % MOD * ( * x + ) % MOD * inv6) % MOD;

}

inline ll f(ll x) {

    return ((x + ) * 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 = ;

        for (int i = ; i * i <= m; i++) {

            if (m % i == ) {

                fac[cnt++] = i;

                while (m % i == ) m /= i;

            }

        }

        if (m != ) fac[cnt++] = m;

        ll ans = cal();

        ll ans0 = ;

        for (int i = ; i < ( << cnt); i++) {

            ll temp = ;

            int sum = ;

            for (int j = ; j < cnt; j++) {

                if (i & ( << j)) {

                    sum++;

                    temp *= fac[j];

                }

            }

            if (sum & ) {

                ans0 = (ans0 + cal(temp)) % MOD;

            } else {

                ans0 = (ans0 - cal(temp) + MOD) % MOD;

            }

        }

        ans = (ans - ans0 + MOD) % MOD;

        printf("%lld\n", ans);

    }

    return ;

}

巴特西

吉首大学2019年程序设计竞赛（重现赛）D - 数列求和(嘤雄难度)

最新文章

热门文章