求该式子，因为只有里面mod 外面没mod；
所以先是把前面的等差数列求和，然后再减去模掉的部分；
这是类欧几里得模板题
1 #include<bits/stdc++.h> 2 #define pd putchar(' ') 3 #define pn putchar('\n') 4 #define pb push_back 5 #define fi first 6 #define se second 7 #define f1(i,j,n) for(int i=j;i<n;i++) 8 #define f2(i,j,n) for(int i=j;i<=n;i++) 9 #define mem(i,j) memset(i,j,sizeof(i)) 10 #define INF 0x3f3f3f3f 11 #define PI acos(-1.0) 12 #define ll long long 13 #define jiasu ios::sync_with_stdio(false) 14 #define P1 printf("YES\n") 15 #define P2 printf("NO\n") 16 const ll mod = 1e9 + 7 ; 17 const ll maxn = 1e5 + 10 ; 18 const double eps = 1e-8 ; 19 using namespace std; 20 ll solve(ll a,ll b,ll c,ll n){ 21 22 //a 公差 b 首项 c 除数 n 项数 23 if(n==1) return b/c; 24 if(n<=0) return 0; 25 ll ans=(a/c)*((n-1)*n/2); 26 ans+=(b/c)*n; 27 a%=c;b%=c; 28 if(a==0)return ans; 29 return ans+solve(c,(a*n+b)%c,a,(a*n+b)/c); 30 } 31 int main() 32 { 33 int t; 34 scanf("%d",&t); 35 while(t--){ 36 ll p,q,n; 37 scanf("%lld%lld%lld",&p,&q,&n); 38 ll sum=p*n*(n+1)/2; 39 ll res=solve(p,p,q,n)*q; 40 printf("%lld\n",sum-res); 41 } 42 return 0; 43 }