Codeforces #10 C Digital Roots

題意﹕定義d(x)為不斷把x的數位取和直至變成個位數為止，例d(199) = d(19) = d(10) = d(1) = 1。給了N，問有多少組(A, B, C)使得1 <= A,B,C <= N，d(d(A)d(B)) = d(C) 但 AB != C。1 <= N <= 10^6。

想了一整天終於AC，方法沒有Petr他們簡單，在這裡說說我的方法。

Observation 1: 若x, y也沒有限制數值，d(d(x)d(y)) = d(xy)。

Observation 2: 對於固定的d(x)，d(d(x)d(y))的值是循環的。因為d(x) = (x-1)%9 + 1，d(x)d(y)即把d(x)向前移d(y)步。又，因為函數d取值在1~9之間，所以會出現循環。

設
A[k] = |{k: 1 <= k <= 9, there exists i, j such that i*j<10 and d(i*j)=k }|
B[k] = |{k: 1 <= k <= 9, there exists i, j such that 10 <= i*j <= N and d(i*j)=k }|
A, B均可以在O(N)內算出。

簡單地想，答案是這樣的﹕
枚舉所有i, j﹕
(1) 如果i*j < 10, 則(i, j, C)的解有B[d(i*j)]個。這是因為B的是d(x*y)的個數，而且x*y > 9，所以B[d(i*j)]的個數均不可能包含i*j。
(2) 如果i*j >= 10，就有點麻煩。首先，符合的解至少有A[d(i*j)]個，原因與(1)相同。但對於B[d(i*j)]，則再細分以下情況﹕
(i) 10 <= i*j <= N，B[d(i*j)]包含了i*j，則需要加上B[d(i*j)]-1，即此情況的(i, j, C)個數有A[d(i*j)]+B[d(i*j)]-1個;
(ii) i*j > N，B[d(i*j)]不包含了i*j，因此加上B[d(i*j)]就可以了，即(i, j, C)的個數有A[d(i*j)]+B[d(i*j)]個。

Observation 1保証了d(d(i)d(j))和d(i*j)相等，所以簡單地用d(i*j)表示就可以了。

這樣枚舉的話複雜度是O(N^2)的，保証過不了。但記得Observation 2說的是，對於固定的i，d(i*j)是一個循環序列。例﹕
i = 2， d(i*j) = {2, 4, 6, 8, 1, 3, 5, 7, 9, 2, 4, 6, 8, 1, 3, 5, 7, 9, ...}
i = 3， d(i*j) = {3, 6, 9, 3, 6, 9, 3, 6, 9, ...}

換角度想，如果對於固定的i，枚舉j的時候條件(1)始終成立，這樣會重覆計算B[d(i*j)]很多次。想避免重覆計算可以先預計算固定d(i)的Partial Sum, SumB[d(i)][0..9]， SumB[d(i)][0] = 0，SumB[d(i)][j] = SumB[d(i)][j-1] + B[d(i*j)]。這樣一來可以直接O(1)取(N/9)*SumB[d(i)][9] + SumB[d(i)][N%9]。同樣的分析可以應用到case (2)(ii)，即預計算SumA[d(i)][0..9]。
但你會發現兩個問題﹕
(a) case (2)(i) 不是很直接的算 SumB[d(i)] - 常數，因為某些B[d(i*j)]根本是0的，硬是減1會出現負數。
(b) 對於固定的i，可以存在[1..j]是case (1)，[j+1..k]是case (2)(i)，[k+1..N]是case (2)(ii)的情況。

對於(a)，只需另開SumC[d(i)][0..9]即可，唯與SumB一不同的是SumC[d(i)][0] = 0，SumC[d(i)][j] = SumC[d(i)][j-1] + max(0, B[d(i*j)]-1)。

對於(b)，顯然j = 9/i，k = N/i。然後用類似如下公式即可﹕ (例如取k+1...N的值)

(N/9)*SumA[d(i)][9] + SumA[d(i)][N%9] - (k/9)*SumA[d(i)][9] + SumA[d(i)][k%9]

然後應用到三段分切的情況。

預計算SumA, SumB和SumC都是O(1)的，對於固定的i計算(i, j, C)的個數均是O(1)的，因此整個算法是O(N)。