逆元模板

对于(a/b)%m==?

1.当m是素数的时候,根据费马小定理,直接输出b^(n-2)即可

2.否则,扩展欧几里得exgcd(b,m,x,y)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 int a,b,m;
 7 int x,y;
 8 int exgcd(int a,int b,int &x,int &y)
 9 {
10     if(b==0)
11     {
12         x=1;
13         y=0;
14         return a;
15     }
16     int r=exgcd(b,a%b,x,y);
17     int tmp=x;
18     x=y;
19     y=tmp-a/b*y;
20     return r;
21 }
22 int fastpow(int a,int p)
23 {
24     int base=a;int ans=1;
25     while(p!=0)
26     {
27         if(p%2==1)ans=ans*base;
28         base=base*base;
29         p=p/2;
30     }
31     return ans;
32 }
33 int main()
34 {
35     scanf("%d%d%d",&a,&b,&m);
36     for(int i=1;i<=sqrt(m);i++)
37     {
38         if(m%i==0)
39         {
40             int ans=exgcd(b,m,x,y);
41             printf("%d",(a*ans)%m);
42             return 0;    
43         }
44     }
45     printf("%d",fastpow(b,m-2));
46 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1245 最小的N个和

    1245 最小的N个和 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description ...

    attack
  • 2017.9.17校内noip模拟赛解题报告

    预计分数:100+60+60=220 实际分数:100+60+40=200 除了暴力什么都不会的我。。。。。 T1 2017.9.17巧克力棒(chocolat...

    attack
  • BZOJ2705: [SDOI2012]Longge的问题(欧拉函数)

    \(ans = \sum_{d | n} d \phi(\frac{n}{d})\)

    attack
  • 1245 最小的N个和

    1245 最小的N个和 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description ...

    attack
  • 2017.9.17校内noip模拟赛解题报告

    预计分数:100+60+60=220 实际分数:100+60+40=200 除了暴力什么都不会的我。。。。。 T1 2017.9.17巧克力棒(chocolat...

    attack
  • XMU oj Problem List

    注意不要有不必要的输出,比如"请输入 a 和 b 的值: ",示例代码见隐藏部分。

    glm233
  • “玲珑杯”ACM比赛 Round #13 题解&源码

    A ? 题目链接:http://www.ifrog.cc/acm/problem/1111 分析:容易发现本题就是排序不等式, 将A数组与B数组分别排序之后,...

    Angel_Kitty
  • AtCoder Beginner Contest 173 A ~ F(已经补完)

    C 思路:二进制枚举 for(int i=0;i<(1<<h);i++) for(int j=0;j<(1<<w);j++) 二进制每次+1就可以暴力遍...

    用户7727433
  • Day4上午解题报告

    预计分数:50 +0+0=50 实际分数:50+0+10=60 毒瘤出题人,T3不给暴力分 (*  ̄︿ ̄)  T1 https://www.luogu.org/...

    attack
  • 【优秀题解】绝对值排序】(合并排序详解+图解)

    原题链接:http://www.dotcpp.com/oj/problem1169.html (大家可以自行提交) 解题思路: 1.采用分治法思想,把整个序列...

    编程范 源代码公司

扫码关注云+社区

领取腾讯云代金券