CF1342C Yet Another Counting Problem

给定两个数 \(a,b\)，进行 \(q\) 次询问，对于每次询问给出回答——在 \([l,r]\) 中，满足以下条件的 \(x\) 的个数：\((x \mod a) \mod b=(x \mod b) \mod a\) 的数的个数。保证 \(l_i,r_i\le 10^{18}\)。

什么时候会合法呢？不难想到取模的周期性。

• 如果 \(x \mod a=y\)，则 \((x+a) \mod a=y\)，进而推得 \((x+a\times k) \mod a=y\)。
• 如果 \(x \mod b=y\)，则 \((x+b) \mod b=y\)，进而推得 \((x+b\times k) \mod b=y\)。
• 如果 \((x \mod a) \mod b=(x \mod b) \mod a\)，不难发现，\(((x+k\times ab) \mod a)\mod b=((x+k\times ab) \mod b)\mod a\)。

循环！ 循环节是 \(a\times b\)。故此，我们只需要预处理出 \(0 \to a\times b-1\) 范围内合法的数，就可以推到任意区间。具体公式是 \(\lceil\frac{x}{ab}\rceil \times sum_{ab-1}+sum_{x\mod ab}\)。

时间复杂度 \(O(ab+q)\)。

下面是预处理：

t=a*b;
for(reg int i=0;i<t;++i){
	if((i%a%b)!=(i%b%a)) s[i]=1;
	for(reg int i=1;i<a*b;++i) s[i]+=s[i-1];
}

下面是查询函数：

inline LL ask(LL x){
	if(x==0) return 0;
	LL y=x/t,res=s[t-1]*y;
	x-=y*t;
	return res+s[x];
}

THE END

CF1342C Yet Another Counting Problem

原文：https://www.cnblogs.com/q0000000/p/15237598.html