馬上得到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; }
沒有留言:
張貼留言