快速乘/龟速乘模板

用于防止大数乘法溢出

//龟速乘O(logn)
int gsc(int a,int b,int p){int res=0;while(b){if(b&1)res=(res%p+a%p)%p;a=(a<<1)%p;b>>=1;}return res;
}
//快速乘O(1)
ll ksc(int a,int b,int p){ll z = (long double)a/p*b;ll res =(ull)a*b -(ull)(z*p);return (res+p)%p;
}