【刷题摘要】6-28 至 7-2 暑假集训前刷题汇总-526互联

Day 1：6-28（+3）

第一天，发现从哪里开始学都要纠结一阵......dp？图论？搜索？发现过了许久有点一下子啃不动 qwq

便先从最基础的算法开始学吧。

今天貌似只复习了快速幂......（悲

(1) 快速幂、快速乘、龟速乘

快速幂

ll quickpow(ll a, ll b, ll p)
{
	ll ans = 1 % p;
	while (b)
	{
		if (b & 1) ans = (ans * a) % p;
		a = (a * a) % p;
		b >>= 1;
	}
	return ans;
}

快速乘

ull quicktimes(ull a, ull b, ull p)
{
    ull ans = 0;
    while(b)
    {
        if(b & 1) ans = (ans + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return ans ;
}

龟速乘

ll quick_mul(ll a, ll b, ll p)
{
	ll res = 0;
	while(b)
	{
		if(b & 1) res = (res + a) % p;
		a = (a + a) % p;
		b >>= 1;
	}
	return res;
}
ll quick_pow(ll a, ll b, ll p)
{
	ll ans = 1 % p;
	while(b)
	{
		if(b & 1) ans = quick_mul(ans, a, p) % p;
		a = quick_mul(a, a, p) % p;
		b >>= 1;
	}
	return ans;
}

快速幂随便写了点东西，貌似已经烂熟于心了，便自己写了思路在纸上。