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

一时失言乱红尘 2023-06-05 12:33 1阅读 0赞

### It’s a Mod, Mod, Mod, Mod World ###

时间限制: 2 Sec 内存限制: 128 MB

#### 题目描述 ####

You are given multiple problems with three integers p, q, and n. Find ![20190401214301_71285.png][]. That is, the first n multiples of p, modulo q, summed. Note that the overall sum has no modulus.

#### 输入 ####

Each input will begin with a line with a single integer W (1≤W≤105 ), which is the number of cases you must solve.  
Each of the next W lines will contain three space-separated integers p, q and n (1≤p, q, n≤106 ),which are the parameters of the problem as described above.

#### 输出 ####

Output W lines, each with the answer for a given instance of the problem, in the order that they appear in the input.

## 样例输入 ##

3
    2 7 2
    1 4 5
    3 8 10

#### 样例输出 ####

6
    7
    37

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 }

转载于:https://www.cnblogs.com/CharlieWade/p/11469097.html

[20190401214301_71285.png]: http://icpc.upc.edu.cn/upload/image/20190401/20190401214301_71285.png