算法每日一题5

竞赛 / 算法 / 每日一题
Word count: 2k   |   Reading time≈ 9 min

每日一题

每日一题系列旨在督促本人坚持算法练习，并期望将之养成一个习惯。

1、RSA解密

lanqiao-603：RSA解密 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月4日

tags：简单数论

分析：\textcolor{red}{分析：}

  1. 实质是快速幂问题，但是由于涉及到的数据太大，因此采用python解决，c++处理的话必须使用__int128类型；

解决代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# lanqiao-603-附
n = 1001733993063167141
d = 212353
c = 20190324
p = 891234941
q = 1123984201
temp = (p-1)*(q-1)
now = 0
for i in range(2, n+1):
    now = i*temp+1
    if(now%d==0):
        print(now//d)# 输出e
        break

# 快速幂计算
def fastPow(a, n, mod):
    res = 1
    a %= mod
    while(n):
        if(n&1):res = (res*a)%mod
        a = a*a%mod
        n = n>>1
    return res
print(fastPow(c, now//d, n))

2、核桃的数量

lanqiao-210：核桃的数量 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月4日

tags：简单数论、LCM

分析：\textcolor{red}{分析：}

  1. 简单题，直接求最小公倍数即可；

解决代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
// 核桃的数量 
int a, b, c;

int lcm(int a, int b){
	return a/__gcd(a, b)*b;// 相除后乘，防止先乘导致溢出	
}

int main() {
	cin>>a>>b>>c;
	int k = lcm(a, b);
	cout<<lcm(k, c);
	return 0;
}

3、Hankson 的趣味题

lanqiao-520：Hankson 的趣味题 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月4日

tags：简单数论、LCM、GCD

分析：\textcolor{red}{分析：}

  1. 若x是b1的因子，有 x*y = b1，y也可能是答案。

  2. 只需要在范围x<=sqrt(b1)内查询，同时判断y就行了。

  3. 但还是超时，因为gcd计算也要花时间，加上一个优化：if(b1%x==0)，表示b1是x的公倍数。

解决代码：

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;
// Hankson 的趣味题
using ll = long long;
ll n;
ll a0, a1, b0, b1;
ll lcm(ll a, ll b){
	return a/__gcd(a, b)*b;
}

int main() {
	cin>>n;
	for(int i=0;i<n;++i){
		cin>>a0>>a1>>b0>>b1;
		ll ans = 0;// 记录满足条件的个数 
		for(ll x=1;x<=sqrt(b1);++x){// b1一定比a1要大 
			if(b1%x==0){// 确保x能整除b1 
				if(__gcd(x, a0)==a1&&lcm(x, b0)==b1)ans++;
				ll y = b1/x;
				if(x==y)continue;// 相等，则不能重复计算
				if(__gcd(y, a0)==a1&&lcm(y, b0)==b1)ans++;
			}
		}
		cout<<ans<<endl; 
	}
	return 0;
}

4、寻找整数

lanqiao-2131：寻找整数 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月4日

tags：简单数论、LCM

分析：\textcolor{red}{分析：}

  1. image-20230404235737258

  2. image-20230404235754817

解决代码：

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;
// 寻找整数
using ll = long long;
const int N = 50;
int mod[N] = {0,0,1,2,1,4,5,4,1,2,9,0,5,10,11,14,9,0,11,18,9,11,11,15,17,9,23,20,25,16,29,27,25,11,17,4,29,22,37,23,9,1,11,11,33,29,15,5,41,46};
ll ans = 2 + mod[2]; // 初始目标正整数为3，满足3%2=1 
ll k = 2;// 以第一个数作为第一个步长 

int main() {
	for(int a=3;a<N;++a){// a为除数 
		while(1){
			if(ans%a==mod[a]){// 如果当前得到的目标正整数ans能够除a余mod[a]，则表明ans=a*index+mod[a]，满足条件 
				k = k/__gcd(k, ll(a))*a;// 求新的步长 
				break;
			}else{
				ans += k;// 根据当前步长改变目标正整数ans的值 
			}
		}
	}
	cout<<ans;
	return 0;
}

5、笨小猴

lanqiao-527：笨小猴 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月5日

tags：简单数论、素数（质数）判断

分析：\textcolor{red}{分析：}

  1. 关键就是质数的判断

解决代码：

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;

bool isPrime(int n){// 判断是否为质数 
	if(n<=1)return false;
	for(int i=2;i<=sqrt(n);++i){
		if(n%i==0)return false;// 有因子，不是质数 
	}
	return true;
}
int maxn = INT_MIN, minn = INT_MAX;
int letter[26];// 存储每个字母出现的次数
string s;

int main() {
	cin>>s;
	int len = s.size();
	for(int i=0;i<s.size();++i)letter[s[i]-'a']++;
	for(int i=0;i<26;++i){
		if(letter[i]==0)continue;
		if(letter[i]>maxn)maxn = letter[i];
		if(letter[i]<minn)minn = letter[i];
	}
	if(len == maxn)minn = 0;// 考虑边界情况 
//	cout<<maxn<<" "<<minn<<endl;
	if(!isPrime(maxn-minn)){
		cout<<"No Answer"<<endl<<0;
	}else{
		cout<<"Lucky Word"<<endl<<maxn-minn;
	}
	return 0;
}

6、最大最小公倍数

lanqiao-1510：最大最小公倍数 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月5日

tags：简单数论、相邻数、互质

分析：\textcolor{red}{分析：}

  1. 最小的公倍数是三个数的质因数相乘，如果有几个质因数相同，则比较两数中哪个数的质因数的个数较多。例如6、7、8的最小公倍数，先分解因子：6=2×3，7=7×1，8=2×2×2，它们的最小公倍数是3×7×2×2×2。

    大于1的两个相邻整数互质，它们没有公共的质因数。如果题目是任选二个数，最大的最小公倍数是N*(N-1)。

  2. 对于连续的三个整数，分两种情况：

    （1）N是奇数。N、N-1、N-2是奇偶奇，结论是这三个数两两互质，三个数的乘积就是最大的最小公倍数。三个数两两互质，也就是说任意一个质数，只在N、N-1、N-2中出现一次。逐个分析质数：

    ​ 质因数2，只在N-1中出现。

    ​ 质因数3，如果在N中出现（设N = 3a），就不会在N-1中出现（这要求N-1 = 3b，无解），也不会在N-2中出现（这要求N-2 = 3b，无解）。

    推广到任何一个质数k，都只会在N、N-1、N-2中出现一次，所以三个数互质。

    （2）N是偶数。

    ​ 如果N为偶数，那么N与N-2最大公约数为2，所以我们要找下一个质数，此时需要考虑N与N-3的关系：

    ​ 如果N能被3整除，则N-3也能被3整除，此时N与N-3不互质，但是N-1与N-3必然互质（N-1、N-3都为奇数），所以N-1、 N-2、N-3；

    ​ 如果N不能被3整除，则N-3也不能被3整除，此时N与N-3互质，所以选择N、N-1、N-3。

  3. 注意是从相邻的3个数开始考虑的

解决代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
// 最大最小公倍数
using ll = long long;
ll n; 
ll ans;// 最大的最小公倍数

int main() {
	cin>>n;
	if(n%2==1)ans = n*(n-1)*(n-2);// n为奇数	奇偶奇 
	else{// n为偶数,n-2也为偶数,因此不考虑,转而继续考虑n-3，依次类推 
		// n 与 n-3比较 
		if(n%3==1)ans = n*(n-1)*(n-3);// 偶奇奇 
		else ans = (n-1)*(n-2)*(n-3);// 奇偶奇	n能被3整除，则(n-3)也能被3整除且为奇数 
	} 
	cout<<ans;
	return 0;
}

7、质数

lanqiao-1557：质数 - 蓝桥云课 (lanqiao.cn)

完成时间：2023年4月5日

tags：简单数论、质数筛

分析：\textcolor{red}{分析：}

  1. 本题实质就是质数筛的使用；

  2. 当数据不是很大时可以采用埃氏筛；如果数据较多，则需要使用欧拉筛（线性筛取，避免重复筛取）。

解决代码：

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 N = 1e3+10;
int prime[N], cnt = 0;
bool bPrime[N]; // true表示的是非质数 ,表示被筛掉 

void getPrime(int n){
	memset(bPrime, false, sizeof(bPrime));// 默认均未被筛掉 
	for(int i=2;i<=n;++i){
		if(!bPrime[i])prime[cnt++] = i;
		for(int j=0;j<cnt&&i*prime[j]<=n;++j){// 线性筛取，避免重复，提升效率 
			bPrime[i*prime[j]] = true;
			if(i%prime[j]==0)break;
		}
	} 
}

int main() {
	int n;
	cin>>n;
	getPrime(n-1);// 题目要求不包含n本身 
	for(int i=0;i<cnt;++i){
		cout<<prime[i]<<" ";
	}
	cout<<"\n"<<cnt;
	return 0;
}
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2023-2024 Guijie Wang
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信