欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

取模运算的一些性质 科学计数法 快速幂

程序员文章站 2022-06-10 17:17:54
一、取模运算的一些性质 (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)% ......

一、取模运算的一些性质

       (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 * c) % p + (b * c) % p) % p 

二、快速乘法取模

计算a*b %p 时 若a,b较大可以这样

typedef long long ll;
ll q_mul(ll a, ll b, ll p)
{ 
    ll ans = 0;
    while (b)
    {
        if(b&1) ans=(ans+a)%p;//只有b的最后一位为1时才会返回1
        //or ans=(ans+(b%2*a)%p)%p;
        a = (a +a) % p;
        b >>= 1;         //将b值向右移一位 原本是101 现在就回变成10
    }
    return ans;
 

三、快速幂

int quickpower(int a, int b)//是求a的b次方
{
    int ans = 1, base = a; 
    while(b > 0)// 
    {
        if(b & 1) 
        ans *= base;   //ans *= base%m;
        base *= base; //如果要求取模 base *=base%m
        b >>= 1;     
    }
    return ans;      //最后输出时还要对ans取模 

}

 

 

 

四、c++科学计数法

double a = 1e3; // a= 1000
double b = 2.3e2;  //b = 230
double c = -1.3e2; //c = -130