经典板题收集___2023-10-24
经典板题收集___2023-10-24
目录
【模板】快速幂
题目描述
给你三个整数 $a,b,p$，求 $a^b \bmod p$。
输入格式
输入只有一行三个整数，分别代表 $a,b,p$。
输出格式
输出一行一个字符串 a^b mod p=s，其中 $a,b,p$ 分别为题目给定的值， $s$ 为运算结果。
样例 #1
样例输入 #1
2 10 9
样例输出 #1
2^10 mod 9=7
提示
样例解释
$2^{10} = 1024$，$1024 \bmod 9 = 7$。
数据规模与约定
对于 $100%$ 的数据，保证 $0\le a,b < 2^{31}$，$a+b>0$，$2 \leq p \lt 2^{31}$。
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int a, b, p;
cin >> a >> b >> p;
int t = b;
long long ans = 1, base = a;
while(b){
if(b & 1) ans = (ans * base) % p;
base = base * base % p;
b >>= 1;
}
printf("%d^%d mod %d=%d", a, t, p, ans);
}
欧拉筛
bool vis[10000010];
int z[10000010], p = 0;
void Sieve(int n)
{
for (int i = 2; i <= n; i++)
{
if (!vis[i])
z[++p] = i;
for (int j = 1; j <= p && i * z[j] <= n; j++)
{
vis[i * z[j]] = 1;
if (i % z[j] == 0)
break; // 如果满足那z[j]一定后面生成数的最小的质因数
}
}
}
vis[i]==true表示i是合数;z[i]存放第i个质数
[1,p]是n内所有质数
[NOIP2012 提高组] 同余方程
题目描述
求关于 $ x$ 的同余方程 $ a x \equiv 1 \pmod {b}$ 的最小正整数解。
输入格式
一行，包含两个整数 $a,b$，用一个空格隔开。
输出格式
一个整数 $x_0$，即最小正整数解。输入数据保证一定有解。
样例 #1
样例输入 #1
3 10
样例输出 #1
7
提示
数据规模与约定
- 对于 $40%$ 的数据，$2 ≤b≤ 1,000$；
- 对于 $60%$ 的数据，$2 ≤b≤ 50,000,000$；
- 对于 $100%$ 的数据，$2 ≤a, b≤ 2,000,000,000$。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
void process(ll a, ll b, ll &x, ll &y)
{
if (!b)
x = 1, y = 0;
else
{
process(b, a % b, y, x);
y -= (a / b) * x;
}
}
int main()
{
ll a, b, x, y;
scanf("%lld%lld", &a, &b);
process(a, b, x, y);
printf("%lld", (x + b) % b);
}