It's a Mod, Mod, Mod, Mod World Kattis

题目链接：

D - It's a Mod, Mod, Mod, Mod World

Kattis - itsamodmodmodmodworld

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

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 # define ll long long
 4 # define inf 0x3f3f3f3f
 5 const int maxn = 2e6+100;
 6 ll cal(ll a, ll b,ll c,ll n){
 7 if(n<=0)return 0;
 8 if(n==1)return (b/c);
 9 ll tmp=0;
10 tmp+=(a/c)*((n-1)*n/2);
11 tmp+=(b/c)*n;
12  a=a%c;
13  b=b%c;
14  if(a==0)return tmp;
15  else return (tmp+cal(c,(a*n+b)%c,a,(a*n+b)/c));
16 }
17 int main(){
18 int T;
19 scanf("%d",&T);
20 while(T--){
21 ll p,q,n;
22 scanf("%lld %lld %lld",&p,&q,&n);
23 ll tot=n*(p+p*n)/2ll;
24 ll tmp=cal(p,p,q,n);
25 tmp*=q;
26 printf("%lld
",tot-tmp);
27 }
28 return 0;
29 }