数学day2-数论maths in acm程序设计竞赛中的

1、费马小定理与素p互质，则aap 1mod1伪素数：n是费马小定理与素p互质，则aap 1mod1伪素数：n是一个正整数，如果存在和n互素的正数a满足1modn，n是基于a的伪- Miller-Rabbin测试：不断的选取不超过n-1的不同基b，计算1mod n是否成立，如果每次- 成立，则n是素辅助以二次探测算法，可以避免将伪素数判成如果p是素数，x21modp解只能是x1或xp- TwiceDetect(longlonga,longlong b,longlongt= TwiceDetect(longlonga,longlong b,longlongt= long longx,while(b&

2、 1)=b=1; y = x = while(t-)erMod(a,b,y= MultiMod(x,x,if(y=1&x!=1&x!=k-1) return 0;x =returny !=1 ?0 :bool MillerRabin(long long longlong bool MillerRabin(long long longlong for (i = 0;i MAX; tmp =rand() % (n -1) + if(TwiceDetect(tmp, n-1,n)!=1) return (i = erMod(a, b, k) =a b%k, b, k) =a * b % P = p1

3、 a1 * p2 P = p1 a1 * p2 a2* * pn 约数和: 1991 Happy O(n + n /2 + n / 3+ + n / n) HOJ2807Patting给定n(n = 10 5)个数，每个数范围1 106，对于每个数ai，输出除ai外所有能够整除aiHOJ2807Patting给定n(n = 10 5)个数，每个数范围1 106，对于每个数ai，输出除ai外所有能够整除ai的数的for i = 2; i * i N; if for i = 2; i * i N; if (tagi) forj =i;j*j -a m a mod m (a a % m = a a

4、/m * (a + b) % m a % m+ b % m mod (a - b) % m a % m- b % m mod (a *b) % m (a % m) * (b % m) mod(a / b) % m (a % m) / (b % m) mod 如何计算a / b % 定理：如果(b, m) = 1, 1如何计算a / b % 定理：如果(b, m) = 1, 1 mod 题目中通常bm且m是一个素数，满足如果b*b -11modm,那么称b1为b在模 定b在模m下存在逆元的充要条件是(b, m) = b -1 b -1 * bb -1 b -1 * b b (m)-1) mod

5、这样，如果(b, m)互素，求解a / b和a*b -1m就缺点：有很强的限制条件(b, m) = 如何计算a / b % 如果(b, m) != 1, 设a / b如何计算a / b % 如果(b, m) != 1, 设a / b % m有：a / b = km + 则：a = kbm + 先计算a % bm = br, 然后再除以b如何计算a / b % 每个素因子pi的个数ki (ki0)如何计算a / b % 每个素因子pi的个数ki (ki0)，之后对每个素因子分别计算pi kim，最优点：适合计算a! / b! % 缺点：a、b HOJ 2342、1528、1953 (POJ 10

6、91、POJ 1619、POJ 1845、POJ 2478、 2342、1528、1953 (POJ 1091、POJ 1619、POJ 1845、POJ 2478、 POJ2480、POJ2603、POJ2649、POJ2773、 POJ 2992、POJ 3292C(n, ans = if (k n k = nC(n, ans = if (k n k = n for (i = 1;i = k; ans = ans * (n i + 1) / 溢出，最好用long 一般n i N nnN N nnNjn-i=1ji会法语的有C人，blah blah，问至少会一种语言会法语的有C人，blah

7、blah，问至少会一种语言2, 3, 4, 1 2, 4, 3, 12, 3, 4, 1 2, 4, 3, 1 | Fnn pa1 a2 1n pa1 a2 1|Ai 2k| Ai AjAk HOJ给定n个数(n10)，求m以内有多少个数能至m = HOJ给定n个数(n10)，求m以内有多少个数能至m = 10, n= 2:3, 3, 4, 6, 89求解前n项(n 求解前n项(n 求解前n项(n 求解前n项(n 的定义所要求的f(n) = Ak-1 * f(n - 1) + Ak-2 * f(n - 2) + . + A0 * f(n-k)，其中f(0).f(k-1)的初构造k * k的矩阵

8、其中定义所要求的f(n) = Ak-1 * f(n - 1) + Ak-2 * f(n - 2) + . + A0 * f(n-k)，其中f(0).f(k-1)的初构造k * k的矩阵其中A =(Ak-1 Ak-2 . A1)，I然后构造一个k*1列向量这样，M*b之后b0的值就是f(k)，以此类推， M n * b然后构造一个k*1列向量这样，M*b之后b0的值就是f(k)，以此类推， M n * b之后b0的值就是f(k-1+n)，算法复 杂度O(k 3 * logn)。求和式：A0 + A1A2对应图论中的路| A I求和式：A0 + A1A2对应图论中的路| A I| IHOJ2471

9、 Learning = 109)H:HOJ2471 Learning = 109)H:利用输入构造26 * 26的邻接矩阵题目所求为A + A2 + + A(L-、在在1. All FromeveryN- one move to a P-Fromeveryitions are P- ition,there1. All FromeveryN- one move to a P-Fromeveryitions are P- ition,thereisition,everymoveistog(x)isthesmallestnon-g(x)isthesmallestnon-egerfoundamongtheSprague-Grundyvaluesofthe followers of x.HOJ 2756Who Will Be TheA vs. B Start HOJ 2756Who