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

上一篇:Android的网络请求之HttpURLConnection封装


下一篇:[Android基础]Android中使用HttpURLConnection