2020.1.9 【牛】華華教月月做數學 快速幂+快速乘 模的性質

時隔兩月，我回來了

學硬體要吐了

終于熬出頭了

今天來玩一下牛客的ak賽

第一t我就不會了

似乎要用什麼歐拉？

那麼我就沒辦法了

查！

然而出乎我的意料

隻需要快速乘和快速幂就可以a

我擦

先貼一發代碼

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll quick_mul(ll a, ll b, ll p) //快速乘 計算 (a*b)%p
{
	ll res = 0; //加法初始化
	while (b > 0)
	{
		if (b & 1)res = (res + a) % p;
		a = (a << 1) % p;
		b >>= 1;
	}
	return res;
}
ll quick_pow(ll a, ll b, ll p) //快速幂 計算 (a^b %p)
{
	ll res = 1;
	while (b > 0)
	{
		if (b & 1)res = quick_mul(res, a, p);
		b >>= 1;
		a = quick_mul(a, a, p);
	}
	return res;
}
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		ll a, b, c; //求 a^b mod p 的值
		scanf("%lld%lld%lld", &a, &b, &c);
		printf("%lld\n", quick_pow(a, b, c));
	}
	return 0;
}

/*
 * ┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
 * │Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│  ┌┐    ┌┐    ┌┐
 * └───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘  └┘    └┘    └┘
 * ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
 * │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
 * ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
 * │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
 * ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
 * │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter  │               │ 4 │ 5 │ 6 │   │
 * ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
 * │ Shift  │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│  Shift   │     │ ↑ │     │ 1 │ 2 │ 3 │   │
 * ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
 * │ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
 * └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
 *
 */
           

出自海星***的部落格

讓我回憶一下

快速乘

ll quick_mul(ll a, ll b, ll p) //快速乘 計算 (a*b)%p
{
	ll res = 0; //加法初始化
	while (b > 0)
	{
		if (b & 1)res = (res + a) % p;
		a = (a << 1) % p;
		b >>= 1;
	}
	return res;
}
           

快速幂

ll quick_pow(ll a, ll b, ll p) //快速幂 計算 (a^b %p)
{
	ll res = 1;
	while (b > 0)
	{
		if (b & 1)res = quick_mul(res, a, p);
		b >>= 1;
		a = quick_mul(a, a, p);
	}
	return res;
}
           

這樣套上快速乘就不會炸了

關于模的性質

模的性質

這個部落格可以看看