NAIPC 2019-It’s a Mod, Mod, Mod, Mod World(类欧几里德模板)

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn=1e5+7;
 5 const ll mod=1e9+7;
 6 ll p,q,n;
 7 //a 公差 b 首项 c 除数 n 项数
 8 ll work(ll a,ll b,ll c,ll n){
 9     if (n<=0) return 0;
10     if (n==1) return b/c ;
11     ll t = 0;
12     t += a/c*(n-1)*n/2+ b/c*n;
13     a = a%c;
14     b = b%c;
15     if (a==0) return t;
16     return t+work(c,(a*n+b)%c,a,(a*n+b)/c);
17 }
18 int main()
19 {
20     int t;
21     scanf("%d",&t);
22     while(t--)
23     {
24         scanf("%lld%lld%lld",&p,&q,&n);
25         ll ans=(p*(n+1)*n/2-q*work(p,p,q,n));
26         printf("%lld\n",ans);
27     }
28     return 0;
29 }