同模余定理
公式
(a+b)%c=(a%c+b%c)%c;
(a-b)%c=(a%c-b%c)%c;
(ab)%c=(a%cb%c)%c;
大数取模
另一类考点就是对大数进行取模
对于大数的求余，联想到进制转换时的方法，得到
举例如下，设大数m=1234,模n
就等于
((((1×10)%n+2%n)%n×10%n+3%n)%n*10%n+4%n)%n
最大公约数
// 先除后乘避免溢出，__gcd参数需为同类型（均为long long） a / __gcd(a, b) * b;
n个数的最小公倍数
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
| #include <bits/stdc++.h>
using namespace std;
long long lcm_n(vector<int> &a)
{
long long result=a[0];
for(int i=1;i<a.size();i++){
long long num=a[i];
result=a[i]/__gcd(result,num)*result;
}
return result;
}
int main ()
{
int n;
while(cin>>n){
vector <int> a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
cout<<lcm_n(a)<<endl;
}
}
|
斐波那契数列
1479
注意取模时机，注意开动态数组的大小，注意循环的条件，注意输出的下标
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include <bits/stdc++.h>
using namespace std;
int main ()
{
int n;
while(cin>>n){
vector<int> a(n+1);
a[0]=1;
a[1]=1;
a[2]=2;
for(int i=3;i<=n;i++){
a[i]=(a[i-1]+a[i-2])%2333333;
}
cout<<a[n]<<endl;
}
}
|
1111
当n较小时写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| #include <bits/stdc++.h>
using namespace std;
int main ()
{
long long a[72]={0,1,1};
for(int i=3;i<72;i++){
a[i]=a[i-1]+a[i-2]+a[i-3];
}
int n;
while(cin>>n){
cout<<a[n+1]<<endl;
}
}
|
2013
斐波那契数列递归写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include <bits/stdc++.h>
using namespace std;
int f(int n){
if(n==0) return 1;
else if(n==1) return 1;
else return f(n-1)+f(n-2);
}
int main ()
{
int n;
cin>>n;
cout<<f(n);
}
|
1724
双变量迭代解法
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
| #include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;
int main ()
{
int n;
cin >> n;
if(n == 0){
cout << 0 % MOD;
return 0;
}
if((n == 1)||(n == 2)){
cout << 1 % MOD;
return 0;
}
long long a=1;
long long b=1;
long long res=0;
for(int i=3;i<=n;i++){
res=(a+b)%MOD;
a=b;
b=res;
}
cout<<res<<endl;
}
|
素数
1013
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 <bits/stdc++.h>
using namespace std;
int main ()
{
int n;
cin >> n;
if(n == 1){
cout << 2 << endl;
return 0;
}
for(int i=n; ; i++){
int flag = 0;
for(int j = 2; j < sqrt(i); j++){
if(i % j == 0){
flag = 1;
break;
}
}
if(flag == 0){
cout << i << endl;
break;
}
}
return 0;
}
|
1355
素数判定，需要用一个flag
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
32
33
| #include <bits/stdc++.h>
using namespace std;
int main ()
{
int n;
while(cin>>n){
int flag=0;
if(n==1){
cout<<"no"<<endl;
continue;
}
if(n==2){
cout<<"yes"<<endl;
continue;
}
for(int i=2;i<=sqrt(n);i++){
if(n%i==0){
flag=1;
break;
}
}
if(flag){
cout<<"yes"<<endl;
}
else
cout<<"no"<<endl;
}
}
|
素数筛选
1375
空格，无素数判断。全部使用标志位
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| #include <bits/stdc++.h>
using namespace std;
int main ()
{
int n;
while(cin>>n){
int meiyou=0;
int kg=1;
int flag=0;
if(n==2){
cout<<-1<<endl;
continue;
}
for(int i=2;i<n;i++){
flag=0;
for(int j=2;j<=sqrt(i);j++){
if(i%j==0){
flag=1;
break;
}
}
if(flag==0&&kg==1){
if(i%10==1){
cout<<i;
kg=0;
meiyou=1;
}
}
else if(flag==0&&kg==0){
if(i%10==1){
cout<<' '<<i;
meiyou=1;
}
}
}
if(!meiyou){
cout<<-1;
}
cout<<endl;
}
}
|
分解质因数
1156
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
32
| #include <bits/stdc++.h>
using namespace std;
int count_num (int a){
int num=0;
while(a%2==0){
num++;
a/=2;
}
for(int i=3;i<=sqrt(a);i+=2){
while(a%i==0){
num++;
a/=i;
}
}
if (a > 1) {
num++;
}
return num;
}
int main ()
{
int n;
while(cin>>n){
cout<<count_num(n)<<endl;
}
}
|
1284（重点）
思路
第一步：把 a 拆成 “最小积木块”（质因数分解）
a 就像一个 “成品积木”，我们要先把它拆成不能再拆的 “基础积木”（质因数）。
- 比如 a=10，拆成 2×5（2 和 5 都是质数，没法再拆）；
- 比如 a=8，拆成 2×2×2（3 个 2）；
- 比如 a=12，拆成 2×2×3（2 个 2 + 1 个 3）。
这些 “基础积木” 的数量是固定的：拼 1 个 10 需要「1 个 2 + 1 个 5」，拼 1 个 8 需要「3 个 2」。
第二步：统计 n! 里有多少块 “基础积木”
n! 是 “从 1 到 n 所有数的乘积”，我们可以把这些数也都拆成 “基础积木”，然后统计每种积木的总数量。
比如 6! = 6×5×4×3×2×1，拆成积木：
6=2×3，5=5，4=2×2，3=3，2=2，1 = 无 → 总共有：4 个 2、2 个 3、1 个 5。
统计技巧（不用全拆）：比如统计 6! 里 2 的数量，直接算「6÷2=3（能被 2 整除的数有 3 个：2、4、6） + 6÷4=1（能被 4 整除的数有 1 个：4，额外多 1 个 2） + 6÷8=0」→ 总共 4 个 2，和拆积木结果一致。
第三步：算 “最多能拼多少个 a”（求最大 k）
拼 1 个 a 需要固定数量的基础积木，我们用 n! 里的积木总数 ÷ 拼 1 个 a 需要的积木数，取最小的那个结果，就是最大的 k。
例子 1（输入 6 10）：
拼 1 个 10 需要「1 个 2 + 1 个 5」；
n! 里有 4 个 2、1 个 5；
2 的数量够拼：4 ÷ 1 = 4 个 10；
5 的数量够拼：1 ÷ 1 = 1 个 10；
因为 5 的数量只够拼 1 个，所以最多只能拼 1 个 10 → k=1。
例子 2（输入 10 12）：
a=12 拆成「2 个 2 + 1 个 3」；
10! 里有 8 个 2、4 个 3；
2 的数量够拼：8 ÷ 2 = 4 个 12；
3 的数量够拼：4 ÷ 1 = 4 个 12；
两者都够拼 4 个，所以 k=4。
例子 3（输入 5 8）：
a=8 拆成「3 个 2」；
5! 里有 3 个 2；
2 的数量够拼：3 ÷ 3 = 1 个 8 → k=1。
核心逻辑总结（一句话）
要让 n! 整除 a^k，本质是 n! 里的 “基础积木（质因数）” 数量，能支撑拼出 k 个 a；而最大的 k，由 “最缺的那块积木” 决定（即各质因数可拼数量的最小值）。
再举个生活化的例子
比如：
- n! 相当于你手里有：4 个鸡蛋、1 个番茄（对应 6! 里的 4 个 2、1 个 5）；
- a 相当于 “番茄炒蛋” 这道菜，做 1 份需要：1 个鸡蛋 + 1 个番茄（对应 10 需要 1 个 2+1 个 5）；
- 你最多能做几份？鸡蛋够做 4 份，但番茄只够做 1 份 → 最多 1 份（k=1）。
注意点
首先，n阶乘超过20就不能正常计算
其次，数组不能被传递，真需要用到数组，使用void，然后传参传进来
然后，找木桶中的最短木板类问题时，int max_k = INT_MAX;max_k = min(max_k, arr_n[i] / arr_a[i]);俗称高开低走
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
32
33
34
35
36
37
38
39
40
41
42
43
| #include <bits/stdc++.h>
using namespace std;
void f(int a,int arr[]){
while(a%2==0){
arr[2]++;
a/=2;
}
for(int i=3;i * i <= a;i+=2){
while(a%i==0){
arr[i]++;
a/=i;
}
}
if(a>1){
arr[a]++;
}
}
int main ()
{
int n,a;
long long num = 1;
cin>>n>>a;
int arr_n[1001] = {0}, arr_a[1001] = {0};
for(int i=2;i<=n;i++){
f(i,arr_n);
}
f(a,arr_a);
int max_k = INT_MAX;
for(int i = 2; i <= 49; i++) {
if(arr_a[i] == 0) continue;
max_k = min(max_k, arr_n[i] / arr_a[i]);
}
cout << max_k << endl;
}
|
1464（重点）
注意点：
如何获取最大素因数？
获取的字符串怎么转化成数字？
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include <bits/stdc++.h>
using namespace std;
int f(int a){
int arr[1000]={0};
int j=0;
int jsq=0;
while(a%2==0){
a/=2;
arr[j++]=2;
jsq++;
}
for(int i=3;i<=sqrt(a);i++){
if(a%i==0){
a/=i;
arr[j++]=i;
jsq++;
}
}
if(a>1){
arr[j++]=a;
jsq++;
}
sort(arr,arr+jsq);
return arr[jsq-1];
}
int main ()
{
int n;
while(cin>>n){
cin.ignore();
string s;
for(int i=0;i<n;i++){
getline(cin, s);
string num_str;
for (char c : s) {
if (c >= '0' && c <= '9') {
num_str += c;
}
}
int num = 0;
if (!num_str.empty()) {
num = stoi(num_str);
}
if (num == 0) {
cout << 0 << endl;
continue;
}
cout<<f(num)<<endl;
}
}
}
|
二分快速求幂
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
| #include <bits/stdc++.h>
using namespace std;
long long f(long long x,long long n,long long mod){
long long result=1;
while(n>0){
if(n&1) result=result*x%mod;
x=x*x%mod;
n>>=1;
}
return result;
}
int main ()
{
long long x,n;
cin>>x>>n;
cout<<f(x,n,233333);
}
|
数学公式
判断共线
不能使用除法会有精度损失，叉乘可以表示围城的平行四边形的面积，即两个向量 “同向程度” 的打分。
- 叉乘 vs 点乘（最关键区别）
✅ 叉乘
公式：
a*d - b*c
作用：
判断两个向量是否共线（是否在一条直线上）
=0 → 共线
≠0 → 不共线
✅ 点乘
公式：
a*c + b*d
作用：
判断两个向量是否垂直！
=0 → 垂直
≠0 → 不垂直
1679
一、核心数学思路
- 建立位置与时间的关系
设时间为t (t≥0)，则：
- 小王的位置：
(x1 + u1*t, y1 + v1*t)
- 小明的位置：
(x2 + u2*t, y2 + v2*t)
- 距离的平方（避免开根号，简化计算）
两点距离的平方公式：
d2(t)=[(x1+u1t)−(x2+u2t)]2+[(y1+v1t)−(y2+v2t)]2
展开整理为二次函数形式 d²(t) = at² + bt + c：
- 令
dx = x1 - x2（初始 x 差），du = u1 - u2（x 方向速度差）
- 令
dy = y1 - y2（初始 y 差），dv = v1 - v2（y 方向速度差）
- 则：a=du2+dv2b=2∗(dx∗du+dy∗dv)c=dx2+dy2
- 求最短距离（分 3 种情况）
二次函数 at² + bt + c 的最小值取决于系数a：
微信
支付宝