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);
}
};
