一些基本公式和算法

c++中保留小数点的位数：

#include <iostream>

#include <iomanip>
using namespace std;
int main( void )
{
    const double value = 12.3456789;
    cout << value << endl; // 默认以6精度，所以输出为 12.3457
    cout << setprecision(4) << value << endl; // 改成4精度，所以输出为12.35
    cout << setprecision(8) << value << endl; // 改成8精度，所以输出为12.345679
    cout << fixed << setprecision(4) << value << endl; // 加了fixed意味着是固定点方式显示，所以这里的精度指的是小数位，输出为12.3457
    cout << value << endl; // fixed和setprecision的作用还在，依然显示12.3457
    cout.unsetf( ios::fixed ); // 去掉了fixed，所以精度恢复成整个数值的有效位数，显示为12.35
    cout << value << endl;
    cout.precision( 6 ); // 恢复成原来的样子，输出为12.3457
    cout << value << endl;
}

View Code

取模运算的性质：

取模运算性质
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p 
 a ^ b % p = ((a % p)^b) % p 
((a+b) % p + c) % p = (a + (b+c) % p) % p
((a*b) % p * c)% p = (a * (b*c) % p) % p
(a+b) % p = ( a % p + b % p ) % p
((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p
重要定理
若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；
若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；
若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)；

View Code

快速幂：

快速幂模板(a^b mod c);;
int PowerMod(int a, int b, int c)  
{  
    int ans=1;  
    a = a%c;  
    while(b>0)  
    {  
   
    if(b%2==1)  
    ans = (ans*a)%c;  
    b = b/2;  
    a = (a*a)%c;  
    }  
    return ans;  
}

View Code

最大公约数：

//辗转相除法
int gcd(int m , int n){
    int r = 0 ;
    while(n){
        r = m%n;
        m = n;
        n = r;
    }
    return m;
}

View Code