TCO 2B

900.

Brief description:

f(x) = x%m==0 未定義
= x/(x%m), otherwise
求在區間 [l, r] 範圍內,對任意的 k>=1, f^k(x) 都有定義的 x 的數目
...

Analysis:

我們設 。。使得答案為 ...
。。考慮遞歸解決。

這樣只需要考慮一次函數的作用。。
。。設 r 為模 m 的餘數。。
我們嘗試對 r 進行分組。。

不妨考慮 m = 6,

1 7 13 ..
2 8 14 ...
3 9 ..
4 10 ..
5 11 ..

1

Case 1:

若 r = 1 顯然都合法。。可以直接計算出來。。。
。。。。更進一步。我們發現.。。對於所有 r ⊥m 互質的情況,做法都是類似的。。。
例如。。觀察上面 r = 5:5 11 17 23 29 35 。。。
。。 /m 後變成:1 x x x x 7 x x x x 13 。。。和 r = 1 的情況是一致的。。
。。。。也就是。。對答案的貢獻為。。ceil(nn, r)。。(這裡的 nn 相當於把 n 壓縮下。.。)

(Tips:注意 nn 這裡是 #define nn ((n-r)/m+1)
。。。。但是實際。。我們大可以留個標記。。
。。然後繼續往下思考。。不必再次就深究 nn 的具體值。。
。。。因為隨著程序結構的清晰。。。這些值可能用不到或者代替或被被約去。。。)

Case 2:
。。若 r \not ⊥ m。。。
。。我們以上面的 r = 4 為例吧。。。。

4 10 14 20 26 30 36 ...
->
1 x x 5 x x 9 ....

實際上就是把 n 壓縮一下。。然後修改一下步長。。。
因為我們的 f() 還需要添加一個步長 d。。初始為 1。。而上面互質的情況相當於一個邊界條件。。d = m。

。。這樣就可以了。。。。

。。。這個演算法跑的很快。。。但是我不會對其進行分析。。。。
。。。這個題我的做法和當時 SRM 622 900 的思維迴路是一樣的。。可是這一次我卻未能作出。。
。。。。主要是對中間 gcd() 一帶的抗性太低了。。。對 pattern 的洞察力不夠。。。。
。。。自始至終都沒有把 【步長】 這則關鍵信息歸納出來。。而是在子問題中不停的嘗試去修改模數 m。。。
。。甚至都一度想到模線性方程和莫比烏斯反演上面去了。。。。

template<class T> inline T ceil(T x, T y){return (x - 1) / y + 1;}

#define nn ((n-r)/r+1)
#define g __gcd(m,r)

int m; LL f(LL n, int d = 1){
    if (n <= 0) return 0; if (d == m) return ceil(n,(LL)m);
    LL res = 0; int mm = min((LL)m, n+1);
    for (int r=1;r<mm;r+=d) res += f(nn,m/g);
    return res;
}

class AlwaysDefined {
public:
	long long countIntegers(long long L, long long R, int W) {
        m = W; return f(R) - f(L-1);
	}
};