20111114

ACM 10006 Carmichael Numbers

一開始以為只要算prime就好了,真是好天真,
馬上得到WA一枚。

Carmichael number的意思:
某數經由Fermat Test算出為質數,
但實際上為合數的數,就稱為Carmichael number。

也就是判斷n是否由Fermat Test算出來是質數,
但實際上是合數即可。

Fermat Test是關鍵,因為要算mod,
雖然跟ACM374,但我那題的解法在這題卻不適用。
一個比較好的算則是mod的分配律:
假設 (a * b) % m,可以拆為:
(a % m) * (b % m)。
同理,a^2 % m可以拆為,
(a % m) * (a % m)。
如此就可以把a^n一路往下拆,拆到n為1或0為止。
然而最大數為64998 ^ 2為4224740004,
所以要用unsigned。

有兩種作法,先算出1到65000的Carmichael number,
若測資為這些數,可直接做輸出。

第二種方法,直接做,但演算法要正確且快速,否則會TL。
判斷數字n是否是質數,是質數的情況下,必不為Carmichael number,
若n滿足Fermat Test,要再判斷n是否為質數。
C語言的&&運算子為short-circuit evaluation,
所以質數判斷放前面,Fermat Test判斷放後面,
會比較快。

/* ACM 10006 Carmichael Numbers
 * mythnc
 * 2011/11/14 16:53:51   
 * run time: 0.144
 */
#include <stdio.h>

#define FALSE 0
#define TRUE  1

int prime(int);
int fermat(int);
unsigned int powermod(int a, int n, int d);

int main(void)
{
    int n;

    while (scanf("%d", &n) && n != 0)
        if (!prime(n) && fermat(n))
            printf("The number %d is a Carmichael number.\n", n);
        else
            printf("%d is normal.\n", n);

    return 0;
}

/* fermat: do Fermat test,
 * if n is prime return TRUE,
 * else return FALSE.
 * WARNING: it means in Fermat test is a prime,
 * maybe it isn't really a prime */
int fermat(int n)
{
    int i;

    for (i = 2; i < n; i++)
        if (powermod(i, n, n) != i)
            return FALSE;

    return TRUE;
}

/* powermod: calculate mod value,
 * in recursive method,
 * return big mod number */
unsigned int powermod(int a, int n, int d)
{
    unsigned int x;

    if (n == 0)
        return 1;
    if (n == 1)
        return a % d;
    
    x = powermod(a, n / 2, d);
    x = x * x % d;
    if (n % 2 == 0)
        return x;
    else
        return x * a % d;
}

/* prime: return TRUE if n is prime,
 * else return FALSE */
int prime(int n)
{
    int i;

    for (i = 3; i * i <= n; i++)
        if (n % i == 0)
            return FALSE;

    return TRUE;
}

沒有留言: