某岛

… : "…アッカリ~ン . .. . " .. .
June 8, 2014

TCO 2B

900.

Brief description:

f(x) = x%m==0 未定义
= x/(x%m), otherwise
求在区间 [l, r] 范围内,对任意的 k>=1, f^k(x) 都有定义的 x 的数目

Analysis:

我们设 $$f(x)$$ 。。使得答案为 $$f(r) – f(l-1)$$…
。。考虑递归解决。

这样只需要考虑一次函数的作用。。
。。设 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);
	}
};