取余运算 同余定理

简单说：

若两个不同整数x、y，和一个整数m，若x%m=y%m，则说x、y同余。
此时，(x-y)%m=0 因为余数被减掉了，剩下的差一定是m的倍数。

x = r 1 ∗ m + a x=r1*m+a x=r1∗m+a
y = r 2 ∗ m + b y=r2*m+b y=r2∗m+b
x − y = m ( r 1 − r 2 ) x-y=m(r1-r2) x−y=m(r1−r2)
x、y同余可表示为： x≡y(mod m)。

• ( x + y ) % p = ( x % p + y % p ) % p (x+y)%p=(x%p+y%p)%p (x+y)%p=(x%p+y%p)%p

假设：
    x = a * p + b; 
    y = c * p + d;
 
则： 
    x % p = b; 
    y % p = d;
 
则：
    (x + y) % p = (a * p + b + c * p + d) % p
                = ((a + c) * p + (b + d)) % p
                = (b + d) % p
                = (x % p + y % p) % p

• ( x ∗ y ) % m = ( ( x % m ) ∗ ( y % m ) ) % m (x*y)%m=((x%m)*(y%m))%m (x∗y)%m=((x%m)∗(y%m))%m

例：求 a b % m a^b%m ab%m

int a = 5, b = 101, m = 3, result = 1;

for(int i=1; i<=b; i++){
    result *= a;
    result %= m;
}

• 高精度取模

#include
#include
using namespace std;
int mod(string a,int b)//高精度a除以单精度b
{
    int d=0;
    for(int i=0;i>a>>b)
    {
        cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5658031.html