퀵 승(템플릿)

쾌속 곱하기는 쾌속 멱의 원리와 마찬가지로 주로 64bit 정수 곱하기일 때 롱롱롱이 터지지만 고정밀도가 너무 번거로운 상황 코드를 쓰는 데 쓰인다

#include

#define ll long long

using namespace std;

inline ll ksc(ll a, ll b, ll mod){
	ll ans = 0;
	while( b > 0 ){
		if( b&1 ) ans = (ans + a) % mod;
		a = ( a + a ) % mod;
		b >>= 1;
	}
	return ans;
}

롱더블로 최적화된 코드도 있어요.

inline ll ksc(ll x, ll y, ll mod)
{
    return ( x * y - (ll) ( (long double) x / mod*y )*mod + mod ) % mod;     
}