今天做了一道賞心悅目的數(shù)學(xué)題：https://www.luogu.com.cn/problem/P4942

用了3種方法，反復(fù)學(xué)習(xí)大佬的思路，優(yōu)化優(yōu)化再優(yōu)化，終于A了。

題目描述：

小凱有一天突發(fā)奇想，寫下了一串?dāng)?shù)字：

例如：時(shí)，數(shù)字為：

? ? ? ? ? ?時(shí)數(shù)字為：

小凱很喜歡數(shù)字 9，所以他想問(wèn)你他寫下的數(shù)字除以 9 的余數(shù)是多少

例如：時(shí)，

輸入格式：

第一行為數(shù)字 Q,表示小凱有 Q 個(gè)問(wèn)題

第 2?到 Q+1 行，每行兩個(gè)數(shù)字 l,r?表示數(shù)字范圍

輸出格式:

對(duì)于每行的問(wèn)題輸出一行，一個(gè)數(shù)字，表示小凱問(wèn)題的回答

看了半天先把題看錯(cuò)了。我和某羅一直以為是??

打了半天發(fā)現(xiàn)樣例都沒(méi)過(guò)，才知道是把題看錯(cuò)了。。。

原來(lái)是要把這些數(shù)字組合成一個(gè)大數(shù)字，從前往后寫就是，然后就沒(méi)轍了。

思來(lái)想去，想到如果一個(gè)數(shù)是$9$的倍數(shù)，那么它的個(gè)位數(shù)字之和也是9的倍數(shù)，既是：

于是有了這樣的代碼：

就是從l到r枚舉，然后拆分?jǐn)?shù)字取模，顯然會(huì)超時(shí)，只有60分。

看著大佬的題解，又有了一個(gè)新的思路，我們可以把上式顛倒一下，也能成立。舉個(gè)例子：

若一個(gè)數(shù)是由多個(gè)數(shù)拼成的，那就不需要再把原數(shù)二次拆開(kāi)，直接把原數(shù)加起來(lái)模$9$就行了。于是有了進(jìn)階版：

也超時(shí)了。那看來(lái)只能用一種能擺脫大循環(huán)的方法了。

有了這個(gè)式子：

對(duì)于每個(gè)數(shù)p ,顯然都有任意整數(shù) n 滿足：

這個(gè)式子左邊可以寫成:

其中有p個(gè)n，那就可以寫成：

顯然，這是p的倍數(shù)。

那在這個(gè)區(qū)間，即l到r中，一定有這個(gè)式子所覆蓋的數(shù)，那這些數(shù)我們就可以不用管了。

只需要計(jì)算這些數(shù)之外的數(shù)

到思考的最后一步，我們可以讓l和r分別模9，相減計(jì)數(shù)后輸出即可。

結(jié)束。

題解參考地址:https://www.luogu.com.cn/blog/ttjb/solution-p4942