ZTL — 数学 — 数论基础模板

zimindaada · 2020-09-11 16:10:31 · 个人记录

    //place these codes after Basic I\O
    bool is_prime(ll x){
        for(ll i = 2; i*i <= x; ++i) if(!(x%i)) return 0;
        return x >= 2;
    }
    ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
    void exgcd(int a, int b, int &x, int &y){
        if(!b) {x = 1, y = 0; return;}
        exgcd(b,a%b,x,y);
        int p = x; x = y; y = p-a/b*y;
    }