题解 P4942 【小凯的数字】

题目

为什么看到很多题解区的 dalao 都用逆元？是我太菜了吧

【分析】

首先，根据弃九验算法的原理，显然可以得到：一个 \(n\) 位数

\(a_1a_2a_3\dots a_n\equiv a_1+a_2+a_3+\dots+a_n(\mod 9)\)

证明：

对于第 \(k\) 位数 \(a_k\) ，它对答案的贡献为\(10^{n-k}\times a_k\%9(n\geq k)\)

当 \(n=k\) 时 \(10^{n-k}=10^{n-n}=1\)

当 \(n>k\) 时 \(10^{n-k}=10^{n-k-1}\times 10\equiv 10^{n-k-1}\times 1\equiv\dots\equiv 10^0=1(\mod 9)\)

所以第 \(k\) 为的 \(a_k\) 贡献为 \(a_k\) 累计得到上式

而对于 \(89101112\) 这样的数字，也同等于：

\(89101112\equiv8+9+1+0+1+1+1+2\equiv8+9+10+11+12(\mod 9)\)

所以我们要求的东西就变为了 \(\displaystyle \sum_{i=l}^ri\%9\)

那么，我们设 \(\displaystyle Last(n)=\sum_{i=1}^ni\%9\)

答案即变为 \(Last(r)-Last(l-1)\) ，当然，记得取正数

现在，问题转变为求解 \(Last(n)\)

\(\displaystyle \because Last(n)=\sum_{i=1}^ni\%9\)

而且 \(1+2+3+4+5+6+7+8+9=45\equiv 0(\mod 9)\)

所以直接有 \(Last(n)=Last(n\% 9)\)

我们 \(9\) 以内的脑算打表，剩下的直接求解即可

【代码】

那本蒟蒻就放我码风极丑的代码了

#include<iostream>

using namespace std;

inline int read(int ans){

    char c=getchar();

    while(c<48||c>57) c=getchar();

    while(c>=48&&c<=57){

        ans+=(c-48);

        c=getchar();

        if(ans>=9) ans-=9;

    }

    return ans;

}

int ar_d_Lst[]={0,1,3,6,1,6,3,1,0};

int main(){

    int q,l,r,ans;

    cin>>q;

    while (q--){

        l=read(8),r=read(0);

        ans=ar_d_Lst[r]-ar_d_Lst[l];

        if(ans<0) cout<<ans+9<<endl;

        else cout<<ans<<endl;

    }

    return 0;

}

最后安利一下本蒟蒻的博客

巴特西

题解 P4942 【小凯的数字】

【分析】

【代码】

最新文章

热门文章