题目大意：
求有多少\(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)\)在查询前预处理。
- 数论 Counting Another Problem 1342C数论counting another problem 题解counting another problem counting another path abc counting atcoder another 259h permutation codeforces another problem another problem range query permutation another problem 1858c minimization another problem 1637d inversions another problem yet partiton another problem 1175g