let a=(k1n+c), b=(k2n+c), ( k1n<=a< (k1+1)n ) && ( k2n<=b<(k2+1)n ) a*b=k1k2n^2 + dk1n + ck2n + cd ab mod n = cd mod n = (a mod n) (b mod n) mod n

 2.1 同余性质1：

    对任意整数b     ab≡bc (mod m) -----------(1)
    证明：         c=a mod m <=> a = km +c
        =>ab = k*b*m+bc => ab mod m = (k*b*m + bc)mod m = bc mod m     (1)式等价于：ab mod m =b* (a mod m) mod m，这非常适合递归计算。

   2.2 同余性质2

    a≡c (mod m) => a2≡c2 (mod m)--------------(2)     证明:         a=k*m+c =>a2=(km)2+2ckm+c2 =>a2 mod m =c2 mod m，即（2）成立
另附poj1995 #include int z, m, h, ans, a, b; int pow_getmod(int a, int b){ int nowmod=a % m, nowans=1; for (int i=b; i>0; i>>=1){ if (i&1) (nowans=nowans* (nowmod) %m); nowmod=nowmod*nowmod % m; } return nowans; } int main(){ scanf("%d", &z); for (int i=0; i