题解：SP20038 SNGLOOP1 - Easiest Loop 1

· · 题解

本题是一道比较水的数学题

求解 S_n 的通项公式

首先，我们来看 S_n 的通项公式。想要求它的通项公式，我们可以先求它的递推式，递推式显然是 S_n = 3S_{n - 1} + 5n，其中 S_0 为一个未知的已知值（？）。

这个式子如果不加上后面的一坨，即 S_n = 3S_{n - 1}，那么通项公式为 S_n=3^nS_0。再看后面，显然，你的后面式子是第 i 个式子时出现的，那么你到 n 一共乘了 n-i-1 个 3。所以合起来的通项公式就是下面一大坨：

S_n = 3^nS_0 + \sum^{n - 1}_{i = 0}3^{n - i - 1}5(i+1)

化简左式

然后，我们把这一坨带回左式

\begin{aligned} LHS&=(2n+3)(p-1) + \frac{4}{5}(3^npS_0 + p\sum^{n - 1}_{i = 0}3^{n - i - 1}5(i+1) - 3^mS_0 - \sum^{m - 1}_{i = 0}3^{m - i - 1}5(i+1))\\ &=(2n+3)(p-1)+\frac{4}{5}(3^npS_0+p\sum_{i=0}^{n-1}3^{n-i-1}5(i+1)-3^mS_0-\sum_{i=0}^{m-1}3^{m-i-1}5(i+1))\\ &=(2n+3)(p-1)+\frac{4}{5}\left[3^npS_0-3^mS_0+p\sum_{i=0}^{n-1}3^{n-i-1}5(i+1)-\sum_{i=0}^{m-1}3^{m-i-1}5(i+1)\right]\\ &=(2n+3)(p-1)+\frac{4}{5}\left[3^npS_0-3^mS_0+\frac{5p}{4}(3^{n+1}-2n-3)-\frac{5}{4}(3^{m+1}-2m-3)\right]\\ &=(2n+3)(p-1)+\frac{4}{5}(3^npS_0-3^mS_0)+p(3^{n+1}-2n-3)-(3^{m+1}-2m-3)\\ &=(2n+3)p-(2n+3)+p3^{n+1}-p(2n+3)-3^{m+1}+2m+3+\frac{4}{5}(p3^n-3^m)S_0\\ &=p3^{n+1}+2m-2n-3^{m+1}+\frac{4}{5}(p3^n-3^m)S_0\\ &=2m-2n+(3+\frac{4}{5}S_0)(p3^n-3^m) \end{aligned}\\

化简右式

再看右式，右式也是非常的简单，即

RHS=2m-2n

求解 p 的值

所以左式等于右式，即

2m-2n+(3+\frac{4}{5}S_0)(p3^n-3^m)=2m-2n\\ \therefore (3+\frac{4}{5}S_0)(p3^n-3^m)=0\\ \therefore p3^n=3^m\\ \therefore p=3^{m-n}\\

这样，我们得到了最终的式子。

求 p 的末尾

最后一步，找规律，显然，3^x 的末尾规律是 3,9,7,1，我们只需要求出 (m - n) 模 4 的余数就可以了，代码如下：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n, m;
        cin>>n>>m;
        int g = m - n;
        g %= 4;
        if(g == 0) cout<<1<<endl;
        if(g == 1) cout<<3<<endl;
        if(g == 2) cout<<9<<endl;
        if(g == 3) cout<<7<<endl;
    }
    return 0;//洛谷你告诉我这是橙，这肯定有个黄啊
}

ok，大功告成，感谢您的观看。（本文耗费作者两个小时，点个赞在走吧，谢谢。