题解

44 条题解

  • 2
    @ 2017-11-08 17:18:15
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <cmath>
    #include <algorithm>
    #define ll long long
    using namespace std;
    ll a,b;
    
    
    
    
    ll exgcd(ll a,ll b,ll &x,ll &y)
    {
        if(b==0)
        {
            x=1;y=0;
            return a;
        }
        ll ret=exgcd(b,a%b,x,y);
        ll buf=x;x=y;y=buf-a/b*y;
        return ret;
    }
    
    
    int main()
    {
        scanf("%lld%lld",&a,&b);
        ll x,y;
        ll gcd=exgcd(a,b,x,y);
      x=(x%b+b)%b;
        printf("%lld",x);
    }
    
  • 2
    @ 2017-10-27 16:46:43

    很裸的扩欧

    #include <iostream>
    #include <iomanip>
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <algorithm>
    #include <cctype>
    #include <vector>
    #include <queue>
    using namespace std;
    int a,b,x,y,k;
    void gcd(int m,int n)
    {
        if(n==0)
        {
            x=1;
            y=0;
            return;
        }
        gcd(n,m%n);
        k=x;
        x=y;
        y=k-m/n*y;
        return;
    }
    int main()
    {
        scanf("%d%d",&a,&b);
        gcd(a,b);
        printf("%d",(x+b)%b);
        return 0;
    }
    
  • 1
    @ 2020-01-29 02:33:55

    pow(a, -1, b) # Python 3.8

  • 1
    @ 2017-10-27 20:43:01

    扩欧

    #include<cstdio>
    #include<cmath>
    using namespace std;
    typedef long long LL;
    void gcd(LL a, LL b, LL &d, LL &x, LL &y) {
        if (!b) {d = a, x = 1, y = 0;}
        else {gcd(b, a % b, d, y, x); y -= x * (a / b); }
    }
    int main() {
        LL a, b, GCD, x, k;
        scanf("%lld %lld", &a, &b);
        gcd(a, b, GCD, x, k);
        LL ta = b / GCD;
        while (x < 0) x += ta;
        printf("%lld", x);
        return 0;
    }
    
  • 1
    @ 2017-10-18 16:49:13
    #include <cmath>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <string>
    #include <vector>
    #include <deque>
    using namespace std;
    
    long long ext_gcd_1(long long a,long long b,long long &x,long long &y)
    {
        if (b==0)
        {
            x=1,y=0;
            return a;
        }
        else
        {
            long long ans=ext_gcd_1(b,a%b,x,y);
            long long temp=x;
            x=y;
            y=temp-(a/b)*y;
            return ans;
        }
    }
    
    long long a,b,x,y;
    
    int main()
    {
        scanf("%lld%lld",&a,&b);
        long long temp=ext_gcd_1(a,b,x,y);
        printf("%lld\n",(x+b)%b);
    }
    
  • 0
    @ 2017-10-12 22:23:00
    #include <iostream>
    #include <algorithm>
    using namespace std;
    #define For(aHJEfaks, fwbjkWK, AENGIBv) for (int aHJEfaks = fwbjkWK; aHJEfaks <= AENGIBv; ++aHJEfaks)
    #define For2(aHJEfaks, fwbjkWK, AENGIBv) for (auto aHJEfaks = fwbjkWK; aHJEfaks != AENGIBv; ++aHJEfaks)
    long long a0, b0;
    typedef pair<long long, long long> pa;
    pa s(long long a, long long b){
        if (a == 1){
            return make_pair(1, 0);
        }
        if (b == 1){
            return make_pair(0, 1);
        }
        if (a > b){
            long long q = a / b;
            long long r = a % b;
            pa tms = s(r, b);
            return make_pair(tms.first, tms.second - q * tms.first);
        }
        if (a < b){
            long long q = b / a;
            long long r = b % a;
            pa tnm = s(a, r);
            return make_pair(tnm.first - q * tnm.second, tnm.second);
        }
    }
    int main(){
        cin >> a0 >> b0;
        long long tem = s(a0, b0).first;
        long long ans = 0;
        if (tem > 0) {
            ans = tem - (tem / b0) * b0;
        }
        if (tem < 0){
            ans = tem - (tem / b0 - 1) * b0;
        }
        cout << ans << endl;
        return 0;
    }
    
    
  • 0
    @ 2017-09-06 18:22:56
    #include <iostream>
    #include <vector>
    #include <cstring>
    #include <queue>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    void exgcd(int a, int b, int &x, int &y)
    {
        if(a==1){
            x=1;y=0;
            return;
        }
        exgcd(b,a%b,x,y);
        int temp=x;
        x=y;
        y=temp-a/b*y;
    }
    int main()
    {
        int a,b,x,y;
        cin>>a>>b;
        exgcd(a,b,x,y);
        if(x<1)x+=b;
        cout<<x<<endl;
        system("pause");
        return 0;
    }
    //此题所用拓展欧几里得算法
    //详见http://blog.csdn.net/zhjchengfeng5/article/details/7786595
    
  • 0
    @ 2017-08-15 21:49:07

    裸地模板题,,

    #include <algorithm>
    #include  <iostream>
    #include   <cstring>
    #include    <cstdio>
    #include     <cmath>
    using namespace std;
    
    void exgcd(int a, int b, int& x, int& y) {
        if(!b) { x = 1; y = 0; return; } 
        int q = a/b, r = a%b;
        exgcd(b, r, y, x);
        y -= q*x;
    }
    
    int inv (int a, int b) {
        int x, y;
        exgcd(a, b, x, y);
        return x;
    }
    
    int main() {
        
        int n, Mod;
        scanf("%d%d", &n, &Mod);
        int sum = inv(n, Mod);
        if(sum < 0) sum += Mod;
        printf("%d", sum);
        
        return 0;
    }
    
  • 0
    @ 2017-05-20 10:39:20

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #define rep(i,n) for(i=1;i<=n;i++)
    using namespace std;
    void exgcd(int a, int b, int &x, int &y){
    if(b==0){
    x = 1; y = 0;
    return;
    }
    exgcd(b,a%b,y,x);
    y -= a/b*x;
    }
    int main(){
    int i, j, n, m, a, b;
    scanf("%d%d", &a, &b);
    exgcd(a,b,n,m);
    printf("%d",(n+b)%b);
    return 0;
    }
    exgcd求逆元裸题= =

  • 0
    @ 2016-11-18 18:25:24
    program
        emod;
    
    uses
        math;
    
    var
        a, b, x, y: longint;
    
    procedure egcd(a, b: longint; var x, y: longint);
    var
        temp: longint;
    begin
        if b = 0 then
        begin
            x := 1;
            y := 0;
            exit;
        end;
        egcd(b, a mod b, x, y);
        temp := x;
        x := y;
        y := temp - (a div b) * y;
    end;
    
    begin
    //    assign(input, 'mod.in'); assign(output, 'mod.out');
    //    reset(input); rewrite(output);
        read(a, b);
        egcd(a, b, x, y);
        while x < 0 do
            inc(x, b);
        write(x);
    //    close(input); close(output);
    end.
    
  • 0
    @ 2016-10-02 13:54:42

    强行不用exgcd(虽然复杂度加了个sqrt())
    由欧拉定理得,如果a和n互质,那么

    a^phi(n) 同余 1(mod n)
    所以
    a^(phi(n)-1) 就是a在mod n意义下的乘法逆元
    算phi是O(sqrt(n))的
    快速幂是O(logn)的
    总复杂度O(sqrt(n))

    #include<bits/stdc++.h>
    using namespace std;
    inline int phi(int x)
    {
        int tail = sqrt(x) + 1e-6;
        int ans = x;
        for (int i = 2;i <= tail;i++)
        {
            if (!(x % i))
            {
                ans = ans / i *(i - 1);
                while (!(x%i))x /= i;
            }
        }
        if (x != 1)ans = ans / x *(x - 1);
        return ans;
    }
    int mod;
    int qpow(int x, int y)
    {
        if (y == 0)return 1;
        if (y == 1)return x;
        if (y == 2)return (long long)x*x%mod;
        if (y == 3)return (long long)x*x%mod*x%mod;
        int tmp = qpow(x, y >> 1);
        tmp = (long long)tmp * tmp % mod;
        if (y & 1)tmp = (long long )tmp * x % mod;
        return tmp;
    }
    int main()
    {
        int a, b;
        scanf("%d%d", &a, &b);
        mod = b;
        printf("%d\n", qpow(a, phi(b) - 1));
    }
    
  • 0
    @ 2016-09-25 22:09:36
    #include <iostream>
    using namespace std;
    
    void gcd(int a, int b, int& x, int& y){
        if(b != 0){
          gcd(b, a%b, x, y);
          int r = x;
          x = y;
          y = r - (a / b) * x;
        }
        else
          x = 1, y = 0;
    }
    
    int main(){
        int a, b, x, y;
        cin>>a>>b;
        gcd(a, b, x, y);
        cout<<(x + b) % b<<endl;
        return 0;
    }
    
  • 0
    @ 2016-09-25 21:56:29
    #include <iostream>
    using namespace std;
    
    void ex_gcd(int a, int b, int& x, int& y){
        if(b != 0){
          ex_gcd(b, a%b, x, y);
          int bri = x;
          x = y;
          y = bri - (a / b) * x;
        }
        else
          x = 1, y = 0;
    }
    
    int main(){
        int a, b, x, y;
        cin>>a>>b;
        ex_gcd(a, b, x, y);
        cout<<(x + b) % b<<endl;
        return 0;
    }
    
  • 0
    @ 2016-09-19 00:23:48

    #include <iostream>
    using namespace std;

    void ex_gcd(int a, int b, int& x, int& y){
    if(b != 0){
    ex_gcd(b, a%b, x, y);
    int bri = x;
    x = y;
    y = bri - (a / b) * x;
    }
    else
    x = 1, y = 0;
    }

    int main(){
    int a, b, x, y;
    cin>>a>>b;
    ex_gcd(a, b, x, y);
    cout<<(x + b) % b<<endl;
    return 0;
    }

  • 0
    @ 2016-09-18 18:36:45
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    typedef long long LL;
    
    void gcd (LL a, LL b, LL &d, LL &x, LL &y) {
        if (!b) { d = a; x = 1; y = 0;}
        else { gcd(b, a%b, d, y, x); y -= x*(a/b);}
    }
    
    int main ()
    {
        freopen("in.txt", "r", stdin);
        LL a, b;
        cin >> a >> b;
        LL d, x, y;
        gcd(a, b, d, x, y);
        if(x < 0) while (x < 0) x += b;
        else while (x > b) x -= b;
        cout << x;
        return 0;
    }
    
  • 0
    @ 2016-09-17 10:40:02

    var
    a,b,x:longint;
    begin
    read(a,b);
    x:=1;
    while (a*x) mod b<>1 do begin
    x:=x+1;
    end;
    writeln(x);
    end.

  • 0
    @ 2016-09-17 10:39:45

    var
    a,b,x:longint;
    begin
    read(a,b);
    x:=1;
    while (a*x) mod b<>1 do begin
    x:=x+1;
    end;
    writeln(x);
    end.

  • 0
    @ 2016-07-13 08:27:58

    同余方程都不知道 ,咋做
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    int x,y;
    void gcd(int a,int b)
    {
    if (a%b==0)
    x=0,y=1;
    else
    {
    gcd(b,a%b);
    int t=x;
    x=y,y=t-(a/b)*y;
    }
    }
    int main()
    {
    int a,b;
    cin>>a>>b;
    gcd(a,b);
    cout<<(x%b+b)%b;
    }

  • 0
    @ 2016-07-12 20:59:31

    就是求乘法逆元,拓展欧几里得算法。
    ~~~
    #include <cstdio>
    int exgcd(int a,int b,int &x,int &y){
    if(b==0){
    x=1;
    y=0;
    return a;
    }
    int ans=exgcd(b,a%b,x,y);
    int temp=x;
    x=y;
    y=temp-(a/b)*y;
    return ans;
    }
    int main(){
    int a,b,x,y;
    scanf("%d%d",&a,&b);
    exgcd(a,b,x,y);
    while(x<=0)x+=b;
    printf("%d\n",x);
    }

信息

ID
1781
难度
4
分类
数论 点击显示
标签
递交数
3860
已通过
1507
通过率
39%
被复制
9
上传者