把常用的数学模板放这里免得忘了

 

素数表

 

1 void Prime() { 2     for (int i = 0;i <= maxn;++i) 3         prime[i] = 1; 4     for (int i = 2; i <= maxn; ++i) { 5         if (prime[i]) { 6             for (int j = 2; i*j <= maxn; ++j) 7                 prime[i*j] = 0; 8         } 9     }10     prime[0] = prime[1] = 0;11     prime[2] = 1;12 }

 

 

 

 

 

 

组合数

1 int cur[maxn][maxn] = { 1 }; 2  3 //预处理 利用杨辉三角计算组合数 4 void init(){ 5     int i, left, right; 6     for (i = 1; i <= maxn; i++){ 7         cur[i][0] = cur[i][i] = 1; 8         left = 1, right = i - 1; 9         while (left <= right){10             cur[i][left] = cur[i - 1][left - 1] + cur[i - 1][left];11             cur[i][right--] = cur[i][left++];//组合数性质cur[i][j]=cur[i][i-j];12         }13     }14 }

 

 

高精度幂取模

1 #include 
      
        2 #include 
       
         3 using namespace std; 4 int main() 5 { 6     unsigned long long b,c,cur,res,i; 7     string a; 8     while(cin>>a){ 9         cin>>b>>c;10         for(i=cur=0;a[i]!='\0';i++){11            cur=cur*10+a[i]-'0';12            cur%=c;13         }14         res=1;15         while(b){16             if(b&1) res=res*cur%c;17             cur=cur*cur%c;18             b>>=1;19         }20         cout<
        
         <
        
       
      

 

模运算法则：

模运算与基本四则运算有些相似，但是除法例外。其规则如下：

(a + b) % p = (a % p + b % p) % p （1）

(a - b) % p = (a % p - b % p) % p （2）

(a * b) % p = (a % p * b % p) % p （3）

(a^b) % p = ((a % p)^b) % p （4）

 

推论：

若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；（10）

若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；（11）

若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，

(a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)； （12）

 

费马定理：若p是素数，a是正整数且不能被p整除，则：a^(p-1) mod p = 1 mod p        

 推论：若p是素数，a是正整数且不能被p整除，则：a^p mod p = a mod p

 

二分快速幂

1 long pow(int x, unsigned int n){2     long p = 1;3     while (n){4         if (n & 1) p *= x;5         x *= x;6         n >>= 1;7     }8     return p;9 }