Codeforces 1342 C

传送门

题目描述：

题意

问 l 到 r 内 有 多 少 个 数 满 足 ( ( x   m o d   a )   m o d   b )   ≠   ( ( x   m o d   b )   m o d   a )               问l到r内有多少个数满足((x\ mod\ a)\ mod\ b)\ \neq\ ((x\ mod\ b)\ mod\ a)\ \ \ \ \ \ \ \ \ \ \ \ \ 问l到r内有多少个数满足((x mod a) mod b) ​= ((x mod b) mod a)             

思路

发 现 当 为 l c a ( a , b ) 倍 数 的 时 候 ， 再 连 续 b 个 数 字 ， 是 那 个 式 子 满 足 相 等 的 。 说 明 循 环 周 期 是 一 个 l c m 我 们 可 以 使 用 前 缀 和 处 理 出 1 − a ∗ b 中 符 合 条 件 的 数 ， 对 于 l 和 r ， 只 需 要 计 算                                  f [ m i n ( n , c n t ) − 1 ] ∗ [ c n t / ( a ∗ b ) + f [ c n t   m o d   ( a ∗ b ) ]                            最 终 答 案 即 c a l c ( r ) − c a l c ( l − 1 )                                                            发现当为lca(a,b)倍数的时候，再连续b个数字，是那个式子满足相等的。说明循环周期是一个lcm\\我们可以使用前缀和处理出1-a*b中符合条件的数，对于l和r，只需要计算\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ f[min(n,cnt)-1]*[cnt/(a*b)+f[cnt\ mod\ (a*b)]\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ 最终答案即calc(r)-calc(l-1)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 发现当为lca(a,b)倍数的时候，再连续b个数字，是那个式子满足相等的。说明循环周期是一个lcm我们可以使用前缀和处理出1−a∗b中符合条件的数，对于l和r，只需要计算                                f[min(n,cnt)−1]∗[cnt/(a∗b)+f[cnt mod (a∗b)]                          最终答案即calc(r)−calc(l−1)                                                          

代码

ll gcd(ll a,ll b){
	return !b?a:gcd(b,a%b);
}
ll a,b,q,l,r,lc;
ll s[maxn];
void init(){
	for(int i=1;i<=lc;i++){
		s[i]=s[i-1]+(i%a%b!=i%b%a);
	}
}

ll cal(ll x){
	return s[lc]*(x/lc)+s[x%lc];
}

int main(){
	int t;
	cin>>t;
	while(t--){
		
		scanf("%lld%lld%lld",&a,&b,&q);
		lc=a*b/gcd(a,b);//最小公倍数 
		init();
		while(q--){
			scanf("%lld%lld",&l,&r);
			printf("%lld ",cal(r)-cal(l-1));
		}
		printf("\n");
	}
}