C++常用代码模板[Magician Van]

//最大公约数（非递归） 
int gcd(int x, int y) {
    int z;
    while (y) {
        z = y;
        y = x % y;
        x = z;
    }
    return x;
}

//2进制快速幂 （x^y % n） 
long long pow(int x, int y, int n) {
    long long p = 1, f = x;
    while (y) {
        if (y & 1) {
            p *= f;
            p %= n;
        } 
        y >>= 1;
        f *= f;
        f %= n;
    }
    return p;    
}

//万进制快速幂 （结合2进制快速幂  a^b % n）
long long pow_10000() {
    char str[Len];
    int a, b[Len], l, n;
    long long ans;
    scanf("%d%s%d", &a, str, &n);
    l = strlen(str);
    for (int i = 0; i <= l - 1; i++) {
        b[(l - i + 3) / 4] *= 10;
        b[(l - i + 3) / 4] += str[i] - ‘0‘;
    }
    l = (l + 3) / 4;
    ans = 1ll;
    for (int i = l; i >= 1; i--) {
        ans *= pow(a, b[i], n);
        ans %= n;
        if (i > 1) ans = pow(ans, 10000, n);
    }
    return ans;
}

//求num的欧拉函数值
int phi_1(int n) {
    int sq = (int) sqrt(n * 1.0) + 1;
    int ans = 1;
    bool flag;
    for (int i = 2; i <= sq; i++) {
        if (n % i == 0) {
            flag = true;
            while (n % i == 0) {
                if (flag) flag = false;    
                else ans *= i;
                n /= i;
            }
            ans *= (i - 1);
        }
    }
    if (n > 1) ans *= (n - 1);
    return ans;
}

//求1~n的欧拉函数 （删减后为筛1~n的素数）
void phi_n(int n) {
    int prime[10000 + 5], phi[100000 + 5], top = 0;
    bool is[100000 + 5];
    for (int i = 1; i <= n; i++) is[i] = true;
    is[1] = false; phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (is[i]) {
            prime[++top] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; j <= top && prime[j] * i <= n; j++) {
            is[prime[j] * i] = false;
            if (i % prime[j] == 0) phi[prime[j] * i] = phi[i] * prime[j];
            else phi[prime[j] * i] = phi[i] * (prime[j] - 1);
        }
    }
}

//判断单个素数
bool isprime(int n) {
    if (n <2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    int t = 4, sq = (int) sqrt(n * 1.0) + 1;
    for (int i = 5; i <= sq; i += t) {
        if (n % i == 0) return false;
        t ^= 6;
    }
    return true;
}