CF1342C Yet Another Counting Problem

时间:2021-09-07 16:21:23   收藏:0   阅读:9

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

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

循环! 循环节是 \(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

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

评论(0)
© 2014 bubuko.com 版权所有 - 联系我们:wmxa8@hotmail.com
打开技术之扣,分享程序人生!