題目大意

??定義函數 $f(n)$ 表示對 $n$ 一直求數位和直至 $n$ 為個位數，即：
$$f(n)=\{\begin{array}{ll}n& n<10,\\ f(g(n))& \text{otherwise,}\end{array}$$

??其中 $g(n)$ 表示 $n$ 的數位和。
??現在有一個很大的 $n$，你要求 $f(n)$。
??這個 $n$ 是根據四個參數 $a,b,m,k$ 生成的，首先生成 $k$ 個數 $a,a+b,a+2b,?,a+(k?1)b$（都在 $\mathrm{m}\mathrm{o}\mathrm{d}m$ 意義下），然后把它們從后往前拼起來，就是 $n$。比如，$a=42,b=42,m=2018,k=18$，會生成 $n=7567146726305885465044624203783362942522101681268442$。

??$0\le a,b\le 10^9,2\le m\le 10^9+7,1\le k\le 10^9$
??多測，$T\le 10^4$

\\
\\
\\

題解

??數論技巧什么的。。還是要時常復習啊。。

??首先這個 $f$ 是有通項公式的，當 $n>0$ 時 $f(n)=(n?1)\mathrm{m}\mathrm{o}\mathrm{d}9+1$，也即 f(n)=(n%9==0) ?9 :n%9。
??所以我們就是要求 $n\mathrm{m}\mathrm{o}\mathrm{d}9$ 的值。（特判 $n=0$）
??注意到 $?x>0,10^x\mathrm{m}\mathrm{o}\mathrm{d}9=1$，因此對于 $n$ 來說，多個數拼起來 $\mathrm{m}\mathrm{o}\mathrm{d}9$ 等價于拆開來 $\mathrm{m}\mathrm{o}\mathrm{d}9$ 再求和，即 $n\mathrm{m}\mathrm{o}\mathrm{d}9={\sum }_{i=0}^{k?1}((a+bi)\mathrm{m}\mathrm{o}\mathrm{d}m)\mathrm{m}\mathrm{o}\mathrm{d}9$。

??注意到這個式子，是先讓 $a+bi$ 模 $m$，再求和，模 $9$。這樣子直接做就不好做，所以要把里面的 $\mathrm{m}\mathrm{o}\mathrm{d}m$ 變形：
$$n\mathrm{m}\mathrm{o}\mathrm{d}9=\sum _{i=0}^{k?1}((a+bi)??\frac{a+bi}{m}??m)\mathrm{m}\mathrm{o}\mathrm{d}9$$
??這樣就變成類歐了。

代碼

#include<bits/stdc++.h> #define fo(i,a,b) for(int i=a;i<=b;i++) using namespace std;typedef long long LL;LL a,b,m,k;LL f(LL a,LL b,LL c,LL n) {if (!a) return (n+1)*(b/c)%9;if (a>=c || b>=c){LL sqr=(n&1) ?(n+1)/2*n :n/2*(n+1) ;sqr%=9;return (f(a%c,b%c,c,n)+(a/c)*sqr+(n+1)*(b/c))%9;} else{LL m=(a*n+b)/c;return (m%9*n%9-f(c,c-b-1,a,m-1)+9)%9;} }int T; int main() {scanf("%d",&T);while (T--){scanf("%lld %lld %lld %lld",&a,&b,&m,&k);a%=m, b%=m;if (a==0 && (k==1 || k>1 && b==0)) {puts("0"); continue;}int ans=((a*k%9+k*(k-1)/2%9*b%9)%9-m*f(b,a,m,k-1)%9+9)%9;printf("%d\n",(ans==0) ?9 :ans);} }

總結

以上是生活随笔為你收集整理的【2017 BSUIR Semifinal G】Digital characteristic 题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。