快速幂

a=2,n=10a = 2, n = 10 的情况为例,注意到 10=21+2310 = 2^1 + 2^3 ,则 2102^{10} 可表示为 221×2232^{2^1}\times2^{2^3} ,利用二进制拆分,可以实现在 O(logn)O(\log_{}{n}) 时间范围内计算出 ana^n 的值。

模板题:洛谷 P1226 | [模板]快速幂||取余运算

题目描述

给你三个整数 b,p,kb,p,k ,求 bpmodkb^p mod k

输入格式

输入只有一行三个整数,分别代表 b,p,kb,p,k

输出格式

输出一行一个字符串 b^p mod k=s,其中 b,p,kb, p, k 分别为题目给定的值, ss 为运算结果。

输入输出样例

输入 #1
1
2 10 9
输出 #1
1
2^10 mod 9=7

说明/提示

样例输入输出 1 解释

210=10241024 mod 9=72^{10} = 1024, 1024\ mod\ 9 = 7

数据规模与约定

对于 100%100\% 的数据,保证 0b,p<2311k<2310\le b,p < 2^{31},1 \leq k \lt 2^{31}

解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <cstdio>
using namespace std;
long long b, p, k;
long long quick_pow(long long base, long long exp, long long mod)
{
if (mod == 1) //任何数模1都等于0
return 0;
if (exp == 0) //任何非零常数的0次方都等于1
return 1;
long long ans = 1;
while (exp)
{
if (exp & 1) //如果末尾为1,则需要乘上该位的指数
{
ans *= base;
ans %= mod; //每步必模
}
base = base * base;
base %= mod;
exp >>= 1;
}
return ans;
}
int main()
{
scanf("%lld %lld %lld", &b, &p, &k);
printf("%lld^%lld mod %lld=%lld", b, p, k, quick_pow(b, p, k));
return 0;
}

最大公约数(GCD)

要求 a,ba, b 的最大公约数,可使用欧几里得辗转相除法。时间复杂度为 O(logn)O(\log_{}{n})

解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <cstdio>
using namespace std;
long long gcd(long long a, long long b)
{
if (a % b)
return gcd(b, a % b);
else
return b;
}
int main()
{
long long a, b;
scanf("%lld %lld", &a, &b);
printf("%lld", gcd(a, b));
return 0;
}

线性筛素数

6oPlEn.png

模板题: 洛谷 P3383 | [模板]线性筛素数

题目描述

给定一个范围 nn ,有 qq 个询问,每次输出第 kk 小的素数。

输入格式

第一行包含两个正整数 n,qn,q,分别表示查询的范围和查询的个数。 接下来 qq 行每行一个正整数 kk ,表示查询第 kk 小的素数。

输出格式

输出 qq 行,每行一个正整数表示答案。

输入输出样例

输入 #1
1
2
3
4
5
6
100 5
1
2
3
4
5
输出 #1
1
2
3
4
5
2
3
5
7
11

说明/提示

样例输入输出 1 解释

210=10241024 mod 9=72^{10} = 1024, 1024\ mod\ 9 = 7

数据规模与约定

对于 100%100\% 的数据, n=108n = 10^81q1061 \le q \le 10^6 ,保证查询的素数不大于 nn

解决方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 100000500;
int n, p, k, cnt;
int prime[maxn / 10];
bool isprime[maxn];
int main()
{
isprime[0] = isprime[1] = true;
scanf("%d %d", &n, &p);
for (int i = 1; i <= n; i++)
{
if (!isprime[i])
{
prime[++cnt] = i;
}
for (int j = 1; i * prime[j] <= n && j <= cnt; j++)
{
isprime[i * prime[j]] = true; //i与小于i的所有素数之积都是合数
if (i % prime[j] == 0) //若i可以整除一个比它小的素数,则停止遍历,保证每个合数只需要标记一次
break;
}
}
for (int i = 1; i <= p; i++)
{
scanf("%d", &k);
printf("%d\n", prime[k]);
}
return 0;
}