hdu 4910 Problem about GCD(數論)

hdu 4910 Problem about GCD(數論)

題目連接：hdu 4910 Problem about GCD

題目大意：給定M，判斷所有小於M並且和M互質的數的積取模M的值。

解題思路：有個數論的結論，若為偶數，M=M/2. 可以寫成M=pk,即只有一種質因子時，答案為M-1，否則為1.特殊情況為4的倍數，不包括4.
首先用1e6以內的素數去試除，如果都不可以為p，那麼對大於1e6的情況判斷一下是否為素數，是素數也可以（k=1），否則開方計算，因為M最大為1e18，不可能包含3個大於1e6的質因子。

#include 
#include 
#include 
#include  // possible need;
#include  // possible need;
#include 
#include 

using namespace std;

typedef long long type;
type mul_mod (type a, type b, type mod) {
    type ret = 0;
    while (b) {
        if (b&1)
            ret = (ret + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return ret;
}

type pow_mod (type a, type n, type mod) {
    type ans = 1;
    while (n) {
        if (n&1)
            ans = mul_mod(ans, a, mod);
        a = mul_mod(a, a, mod);
        n >>= 1;
    }
    return ans;
}

bool miller_rabin(type n) {
    if (n < 2)
        return false;

    srand(time(0));
    for (int i = 0; i < 20; i++)
        if (pow_mod(rand() % (n-1) + 1, n-1, n) != 1)
            return false;
    return true;
}

typedef long long ll;
const int maxn = 1e6;

bool vis[maxn+5];
int np, pri[maxn+5];

void prime_table (int n) {
    np = 0;
    memset(vis, 0, sizeof(vis));

    for (int i = 3; i <= n; i += 2) {
        if (vis[i])
            continue;
        pri[np++] = i;
        for (int j = i * 2; j <= n; j += i)
            vis[j] = 1;
    }
}

bool judge (ll M) {
    if (M % 2 == 0)
        M /= 2;

    for (int i = 0; i < np; i++) {
        ll tmp = M;
        while (tmp % pri[i] == 0)
            tmp /= pri[i];
        if (tmp == 1)
            return true;
    }

    if (M <= 1000000LL)
        return false;

    if (miller_rabin(M))
        return true;

    ll x = sqrt(M+0.0);
    while (x * x < M)
        x++;

    if (x * x != M)
        return false;

    if (miller_rabin(x))
        return true;
    return false;
}

int main () {
    ll M;
    prime_table(maxn);

    //srand(time(0));
    while (scanf("%I64d", &M) == 1 && M != -1) {
        if (M == 1 || M == 2 || M == 4 || judge(M))
            printf("%I64d\n", M-1);
        else
            printf("1\n");
    }
    return 0;
}