数论:逆元,扩展欧几里得模板

https://www.cnblogs.com/neopenx/p/4093951.html

#include "cstdio"
#define LL long long
LL ex_gcd(LL a,LL b,LL &x,LL &y)
{
    if(a==0&&b==0) return -1;
    if(b==0) {x=1;y=0;return a;}
    LL d=ex_gcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}
LL mod_reverse(LL a,LL n)
{
    LL x,y,d=ex_gcd(a,n,x,y);
    if(d==1) return (x%n+n)%n;
    else return -1;
}
int main()
{
    LL T,n,B;
    scanf("%I64d",&T);
    while(T--)
    {
        scanf("%I64d%I64d",&n,&B);
        LL x=mod_reverse(B,9973);
        printf("%I64d\n",(n*x)%9973);
    }
}
全部评论

相关推荐

05-01 22:41
中南大学 Java
点赞 评论 收藏
分享
牛客383479252号:9,2学生暑期实习失利开始投小厂,给这群人整自信了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务