Kattis

题意：计算$sumlimits_{i=1}^n[(p{cdot }i)mod{q}]$

类欧模板题，首先作转化$sumlimits_{i=1}^n[(p{cdot}i)mod{q}]=sumlimits_{i=1}^n[p{cdot}i-leftlfloorfrac{p{cdot}i}{q} ight floor{cdot}q]$，然后只要能快速计算$sumlimits_{i=1}^nleftlfloorfrac{p{cdot}i}{q} ight floor$就行了。

记$f(a,b,c,n)=sumlimits_{i=0}^nleftlfloorfrac{ai+b}{c} ight floor$

则有$f(a,b,c,n)=left{egin{matrix}egin{aligned}&(n+1)leftlfloorfrac{b}{c} ight floor,a=0\&f(a\%c,b\%c,c,n)+frac{n(n+1)}{2}leftlfloorfrac{a}{c} ight floor+(n+1)leftlfloorfrac{b}{c} ight floor,a>=c:or:b>=c\&nleftlfloorfrac{an+b}{c} ight floor-f(c,c-b-1,a,leftlfloorfrac{an+b}{c} ight floor-1),othersend{aligned}end{matrix} ight.$

由于递推过程类似欧几里得法求gcd，因此称作类欧~~

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N=1e5+10;
 5 int p,q,n;
 6 ll f(ll a,ll b,ll c,ll n) {
 7     if(!a)return (n+1)*(b/c);
 8     if(a>=c||b>=c)return f(a%c,b%c,c,n)+n*(n+1)/2*(a/c)+(n+1)*(b/c);
 9     ll m=(a*n+b)/c;
10     return n*m-f(c,c-b-1,a,m-1);
11 }
12 int main() {
13     int T;
14     for(scanf("%d",&T); T--;) {
15         scanf("%d%d%d",&p,&q,&n);
16         printf("%lld
",(ll)n*(n+1)/2*p-f(p,0,q,n)*q);
17     }
18     return 0;
19 }