3
27
2010
0

数论模板

 

ll mul_mod(ll x, ll y, ll n){
	// V x -> ( x = a T + b, 0 <= a <= T, 0 <= b < T ) 
	x %= n;
	y %= n;
	ll T = floor( sqrt(n) + 0.5 );

	// |t| < T
	ll t = T * T - n;

	ll a = x / T; ll b = x % T;
	ll c = y / T; ll d = y % T;
	ll e = a * c / T; ll f = a * c % T;
	
	ll v = ( ( a * d + b * c ) % n + e * t ) % n;
	ll g = v/T; ll h = v % T;
	ll ans =(( (f+g) * t % n + b * d ) % n + h * T ) % n;
	while(ans<0)ans+=n;
	return ans;
}


ll pow_mod(ll a, ll n, ll p){
	ll d = a % p;
	ll ans = 1;
	for(; n; n>>=1){
		if(n&1) ans = mul_mod( ans, d, p );
		p = mul_mod( d, d, p );
	}
	return ans;
}

 

 

Category: 未分类 | Tags: | Read Count: 945

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com