【1342C】Yet Another Counting Problem（数论）

题目大意：

求有多少\(x(1\le l\le x\le r\le 10^{18})\)满足\((x\mod a)\mod b\neq(x\mod b)\mod a(1\le a,b\le 200)\)，有\(q(1\le q\le 500)\)次询问。

设答案为\(f(l,r)\)，考虑前缀和\(f(l,r)=f(1,r)-f(1,l-1)\),现在问题在于计算\(f(1,x)(1\le x\le 10^{18})\)。

我们可以发现规律：对于确定的\(x\)、\(y\)和任意的\(n\)，有\(f(x,y)=f(x+nab,y+nab)\)。

所以\(f(1,ab)=f(ab+1,2ab)=f(2ab+1,3ab)=......=f((n-1)ab+1,nab)\)。

将上式变形，得到\(f(1,2ab)=2f(1,ab),f(1,3ab)=3f(1,ab),......,f(1,nab)=nf(1,ab)\)。

设\(x\mod ab=k\)，则\(x=\lfloor\frac{x}{ab}\rfloor ab+k\)。

所以\(f(1,x)=f(1,\lfloor\frac{x}{ab}\rfloor ab+k)=f(1,\lfloor\frac{x}{ab}\rfloor ab)+f(\lfloor\frac{x}{ab}\rfloor ab+1,\lfloor\frac{x}{ab}\rfloor ab+k)\)

\(=\lfloor \frac{x}{ab}\rfloor f(1,ab)+f(1,k)\)

上式中的\(f(1,ab)\)和\(f(1,k)\)在查询前预处理。