# 类欧几里得算法

0
10

$$\sum_{i=1}^n [(pi)\,mod\,q]$$，其中$$1 \le p,n,q \le 10^6$$,$$1 \le t \le 10^4$$,限时$$1s$$

$$f(a,b,c,n)=\sum_{i=1}^n \lfloor\frac{ai+b}{c} \rfloor$$

$$f(a,b,c,n)=\sum_{i=1}^n \lfloor\frac{ai+b}{c}\rfloor =\sum_{i=1}^n \lfloor\frac{c\lfloor\frac{a}{c}\rfloor i+(a\,mod\,c)i+b\,mod\,c+c\lfloor \frac{b}{c} \rfloor}{c} \rfloor =\sum_{i=1}^n \lfloor\frac{(a\,mod\,c)i+b\,mod\,c}{c} \rfloor+\sum_{i=1}^n \lfloor \frac{a}{c} \rfloor i+ \lfloor \frac{b}{c} \rfloor$$

$$\lfloor x+y \rfloor =\lfloor x \rfloor + y$$

$$\frac{1}{2} \lfloor \frac{a}{c} \rfloor n^2+\frac{1}{2}(\lfloor \frac{a}{c} \rfloor+2\lfloor\frac{b}{c}\rfloor)n$$

1.特殊情况:

$$a=0$$

$$f(a,b,c,n)=\sum_{i=1}^n \lfloor\frac{b}{c} \rfloor=\lfloor\frac{b}{c} \rfloor n$$

2.一般情况：
$$a>0$$
$$\sum_{i=1}^n \lfloor \frac{ai+b}{c} \rfloor$$
$$=\sum_{i=1}^n \sum_{j=1}^{\lfloor\frac{ai+b}{c}\rfloor} 1$$
$$=\sum_{i=1}^n \sum_{j=1}^{\lfloor\frac{an+b}{c}\rfloor} (j\le \lfloor\frac{ai+b}{c}\rfloor)$$

$$=\sum_{j=1}^{\lfloor\frac{an+b}{c}\rfloor} \sum_{i=1}^n (j\le \lfloor\frac{ai+b}{c}\rfloor)$$

$$j\le \lfloor\frac{ai+b}{c}\rfloor$$
$$\Leftrightarrow cj\le ai+b$$

$$\Leftrightarrow ai \ge cj-b$$
$$\Leftrightarrow i \ge \frac{cj-b}{a}$$
$$\Leftrightarrow i \ge \lceil \frac{cj-b}{a}\rceil$$

$$\Leftrightarrow i \ge \lceil \frac{cj-b}{a}\rceil$$
$$\Leftrightarrow i \ge \lfloor \frac{cj-b+a-1}{a}\rfloor$$

$$=\sum_{j=1}^{\lfloor\frac{an+b}{c}\rfloor} \sum_{i=1}^n i \ge \lfloor \frac{cj-b+a-1}{a}\rfloor$$

$$\lfloor \frac{cj-b+a-1}{a}\rfloor \ge \lfloor \frac{c-b+a-1}{a}\rfloor = 1+\lfloor \frac{c-b-1}{a}\rfloor \ge 1$$
$$\lfloor \frac{cj-b+a-1}{a}\rfloor \le \lfloor \frac{c\lfloor\frac{an+b}{c}\rfloor-b+a-1}{a}\rfloor \le \lfloor \frac{an+b-b+a-1}{a}\rfloor =n$$

$$=\sum_{j=1}^{\lfloor\frac{an+b}{c}\rfloor} n-\lfloor \frac{cj-b+a-1}{a}\rfloor+1$$

$$=\sum_{j=1}^{\lfloor\frac{an+b}{c}\rfloor} n-\lfloor \frac{cj-b-1}{a}\rfloor$$

$$=n(\lfloor\frac{an+b}{c}\rfloor)-\sum_{j=1}^{\lfloor\frac{an+b}{c}\rfloor}\lfloor \frac{cj-b-1}{a}\rfloor=n(\lfloor\frac{an+b}{c}\rfloor)-f(c,-b-1,a,\lfloor\frac{an+b}{c}\rfloor)$$

$$f(a,b,c,n)=(\lfloor\frac{an+b}{c}\rfloor)n\frac{1}{2} \lfloor \frac{c}{a} \rfloor \lfloor\frac{an+b}{c}\rfloor^2-\frac{1}{2}(\lfloor \frac{c}{a} \rfloor+2\lfloor\frac{-b-1}{a}\rfloor)\lfloor\frac{an+b}{c}\rfloor-f(c\,mod\,a,(-b-1)\,mod\,a,a,\lfloor\frac{an+b}{c}\rfloor)$$

$$gcd(a,b)=gcd(b\,mod\,a,a)$$（假设第一个参数<第二个参数）

$$f(0,b,c,n)=\lfloor\frac{b}{c} \rfloor n$$

$$a \ge c$$时

$$f(a,b,c,n)=f(a\,mod\,c,b\,mod\,c,c,n)+\frac{1}{2} \lfloor \frac{a}{c} \rfloor n^2+\frac{1}{2}(\lfloor \frac{a}{c} \rfloor+2\lfloor\frac{b}{c}\rfloor)n$$ （等式1）

$$a<c$$时

$$f(a,b,c,n)=(\lfloor\frac{an+b}{c}\rfloor)n-f(c,-b-1,a,\lfloor\frac{an+b}{c}\rfloor)$$ （等式2）

$$\sum_{i=1}^n [(pi)\,mod\,q]$$

$$=p\frac{n(n+1)}{2}-qf(p,0,q,n)$$

<

0