逆元

题目连接：https://scut.online/problem.php?id=97
算出
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 #define ll long long
 6 
 7 ll qpow(ll a,ll b, ll m)
 8 {
 9     ll ans=1,temp=a%m;
10     while(b)
11     {
12         if(b&1) ans=(ans*temp)%m;
13         b>>=1;
14         temp=(temp*temp)%m;
15     }
16     return ans;
17 }
18 
19 int main()
20 {
21     int y,p,k;
22 
23     int t;
24     scanf("%d",&t);
25     while(t--)
26     {
27         scanf("%d%d%d",&y,&k,&p);
28         ll ans=0;
29         if(y!=0)
30         {
31             ll inv=qpow(y,p-2,p);  //求逆元
32             int n=min(1000000,p-1);
33             k=min(k,n);
34             for(int i=0;i<=k;i++)
35             ans=ans+(i*inv%p);
36         }
37         else
38             ans=(p-1)*p/2;
39         printf("%lld
",ans);
40     }
41 }