次方求模-大数求模

次方求模

乘法取模：xy mod n = (x mod n)(y mod n)mod n

加法取模: (x + y)mod n = ((x mod n) + (y mod n)) mod n

int powmod(int n, int p, int mod)
{
    int result = 1;
    while(p > 0)
    {
        if( p % 2 == 1)
        {
            //若n^p不可以整拆分为n^(p/2)和n^(p/2)
            result = (result*n)%mod;
        }
        p /= 2;
        n = (n*n)%mod;
    }
    return result;
}

大数求模

利用到公式：(a+b) mod (n) = ((a mod n) + (b mod n)) mod (n)；

int DivMod(char ch[],int mod){
	int i,result=0;
	for(i=0;ch[i]!='\n';i++)
		result=(result*10+ch[i]-'0')%mod;
	return result;
}