【No.20】蓝桥杯简单数论下|寻找整数|素数的判断|笨小猴|最大最小公倍数|素数筛|埃氏筛|欧氏线性筛|质数|分解质因子(C++)

寻找整数

【题目描述】
有一个不超过 $10^17$ 的正整数n，知道这个数除以2至49后的余数如下表所示，求这个正整数最小是多少
![[Pasted image 20240326202941.png]]

解法一：模拟

暴力法：一个个检验 $1\dots 10^{17}$ 的每个数
由于这个数n最大可能是 $10^{17}$ ，验证的时间太长

解法二：LCM

从表格的第一个数2开始，逐个增加后面的数，找满足条件的n

满足第一个条件，除以2余1的数有：3，5，7，9…此时步长k=2
继续满足第二个条件，除以3余2的数，只能从上一步骤的3，5，7，9…中找，有5，11，17…此时步长k=6
为什么k=6
因为LCM：k=(2, 3)=6

证明:
设 $n_{1}$ 和 $n_{2}$ 满足
$n_{1}= 2a_{1}+1 = 3b_{1}+2$
$n_{2}=2a_{2}+1= 3b_{2}+2$
$n_{2}$ 和 $n_{1}$ 的差 $k=n_{2}-n_{1}=2(a_{2}-a_{1})=3(b_{2}-b_{1})$
k是2的倍数，也是3的倍数，那么k是2和3的最小公倍数，k=lcm(2，3)=6
3. 继续满足第三个条件，除以4余1的数，只能从5，11，17…中找，有5，17，29…此时步长k=lcm(2, 3, 4)=12
4. 继续满足第四个条件…
逐个检查表格，直到满足表格中所有的条件
计算量极小。只需要对表格中的2~49做48次LCM即可

#include <bits/stdc++.h>
using namespace std;
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};
int main()
{
	long long ans = 2 + mod[2l;
	long long k = 2;
	//从第一个数的步长开始
	for(int i = 3; i < N; i ++)
	{
		while(true)
		{
			if(ans % i == mod[i])
			{ 
				//ans是满足前i个数的解
				k=k / __gcd(k，(long long)i)*i;
				//连续做LCM
				break;
			}
			else 
			{
				ans += k;	//累加新的步长
			}
		}
	}
	cout<<ans<<endl;
	return;
}

素数的判断

素数定义：只能被 1 和自己整除的正整数。
注：1 不是素数，最小素数是 2。
判断一个数 n 是不是素数：当n≤10^14时，用试除法；n > 10^14 时，试除法不够用，需要用高级算法，例如 Miller_Rabin 算法。
试除法： 用[2,n-1]内的所有数去试着除 n，如果都不能整除，就是素数。
优化：把[2,n-1]缩小到2到 $\sqrt{ n }$ 。证明：若 n = a x b, 设 a≤ $\sqrt{ n }$ ,则 b≥ $\sqrt{ }$ ,如果 a 是 n 的因子，说明 n 不是素数，b 不用再试且 b 一定也是。

#include <iostream>
#include <cmath>

bool is_prime(long long n){
    if(n <= 1)
        return false; // 1不是素数
    for(long long i = 2; i <= sqrt(n); i++)
        if(n % i == 0)
            return false; // 能整除，不是素数
    return true; // 全不能整除，是素数
}

int main() {
    long long number = 29; // 例子：要检查是否为素数的数值
    if (is_prime(number))
        std::cout << number << " 是素数。" << std::endl;
    else
        std::cout << number << " 不是素数。" << std::endl;
    return 0;
}

因为sqrt求出的数不一定是整数，它其实是double的
加一个判断

k = sqrt(n);
if (k * k != n)
	k += 1;

笨小猴

【题目描述】
笨小猴的词汇量很小，所以每次做英语选择题的时候都很头疼。但是他找到了一种方法，经试验证明，用这种方法去选择选项的时候选对的几率非常大!这种方法的具体描述如下:
假设maxn是单词中出现次数最多的字母的出现次数，minn是单词中出现次数最少的字母的出现次数
如果maxn-minn是一个质数，那么笨小猴就认为这是个Lucky word，这样的单词很可能就是正确的答案。
【输入描述】
输入文件只有一行，是一个单词，其中只可能出现小写字母，并且长度小于100。
【输出描述】输出文件共两行，第一行是一个字符串，假设输入的的单词是Lucky word，那么输出“Lucky Word”，否则输出“No Answer”;
第二行是一个整数，如果输入单词是Lucky Word，输出maxn-minn的值，否则输出0。

模拟，统计每个字母出现的次数，然后判断

#include <bits/stdc++.h>
using namespace std;
int letter[26] = {0};//统计每个字母的个数，是一个hash表
int is_prime(int n)
{
	if(n <= 1)
		return 0;
	for(int i = 2; i <= sqrt(n); i ++)
		if(n % i == 0)
			return 0;
	return 1;
int main()
{
	int maxn = -1, minn = 1000;
	string s;
	cin >> s;
	int len = s.length();
	for(int i = 0; i < len; 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;
	int ans = is_prime(maxn - minn);
	if(!ans)
		cout << "No Answer\n" << 0 << "\n";
	else
		cout << "Lucky Word\n" << maxn - minn << "\n";
	return 0;
}

最大最小公倍数

【题目描述】
已知一个正整数n，问从1~N中任选出三个数，他们的最小公倍数最大可以为多少。
【输入描述】
一个正整数N。
【输出描述】
一个整数表示答案

思路质数的性质

贪心，从大的数开始选，不过，简单地把N里面最大的三个数相乘，N*(N-1)*(N-2)，并不正确，需要分析多种情况

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

大于1的两个相邻整数互质，它们没有公共的质因数。如果题目是任选二个数，最大的最小公倍数是N*(N-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中出现一次，所以三个数互质。
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

#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long n, ans;
	cin >> n;
	if(n <= 2)
		ans = n;
	else if(n % 2)  //n是奇数
		ans = n * (n - 1) * (n - 2); 
	else   //n是偶数
	{   
		if(n % 3)      //n没有因数3
			ans = n * (n - 1) * (n - 3);  
		else          //n有因数3
			ans = (n - 1) * (n - 2) * (n - 3);
	}
	cout << ans;
	return 0;
}

素数筛

素数的筛选：给定 n，求 2~n 内所有的素数。
一个个地判断很慢，所以用“筛子”筛所有的整数，把非素数筛掉，剩下的就是素数。
常用两种筛法：埃氏筛、欧拉筛。
埃氏筛:
初始队列{2、3，4，5，6，7，8，9，10，11，12，13，…，n}
操作步骤：

输出最小的素数 2，筛掉 2 的倍数，得{2，3，4，5，6，7，8，9，10，11，12，13，…}
输出最小的素数 3，筛掉 3 的倍数，得{2，3，4，5，6，7，8，9，10，11，12，13，…}
输出最小的素数 5，筛掉 5 的倍数，得{2，3，4，5，6，7，8，9，10，11，12，13，…}
继续以上步骤，直到队列为空。

int primes[N], cnt;
bool bprime[N];
void getPrime(int n)
{
    memset(bprime, false, sizeof(bprime));
    bprime[0] = true;
    bprime[1] = true;

    for(int i = 2; i <= n; i ++)
    {
        if(!bprime[i])
        {
            prime[cnt++] = i;
            for(LL j = i * 2; j <= n; j += i)
                bprime[j] = true;
        }
    }
}

但是埃氏筛法的缺点：例如 6 会被 3 整除，6 会被 2 整除，会被筛两次，所以我们再给出欧氏线性筛法：

int primes[N], cnt;
bool bPrime[N];
void getPrimes(int n)
{
    memset(bPrime, false, sizeof(bPrime));
    for(int i = 2; i <= n; i ++)
    {
        if(!bPrime[i])
            primes[cnt++] = i;
        for(int j = 0; j < cnt && i * primes[j] < n; j ++)
        {
            bPrime[i * primes[j]] = true;
            if(i % primes[j] == 0)
                break;
        }
    }
}

质数 lanqiaoOJ 题号 1557

【题目描述】
给定一个正整数 N，请你输出 N 以内（不包含 N）的质数以及质数的个数。
【输入描述】
一个正整数 N，n<1000
【输出描述】
两行，第 1 行包含若干个素数，从小到大输出，用空格分开。
第 2 行一个整数，表示素数个数。
输入：

输出：

2 3 5 7 
4

题目为模板题目，实现方式如下，其中：

bprime[i]记录数 i 的状态，若 bprime [i]=1，表示它被筛掉，不是素数。
用 primes[]存放素数，prime[0]是第一个素数 2。
cnt 是素数个数计数

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
int primes[N], cnt;
bool bprime[N]; //true表示被筛掉，不是素数
void getPrimes(int n)  //埃氏筛，计算[2, n]内的素数
{   
	memset(bprime, false, sizeof(bprime));
	bprime[0] = true;
	bprime[1] = true;

	for(int i = 2; i <= n; i ++)
	{
		if(!bprime[i])
		{
			primes[cnt++] = i;
			for(int j = i * 2; j <= n; j += i)
				bprime[j] = true;
		}
	}
}

int main(){
    int n;
    cin >> n;
    getPrimes(n - 1);
    for(int i = 0; i < cnt; i ++)  
	    cout << primes[i] << " ";
    cout << endl;
    cout << cnt;
}

分解质因子

任何一个正整数 n 都可以唯一地分解为有限个素数的乘积： $n=p_{1}^{c_{1}}p_{2}^{c_{2}}p_{3}^{c_{3}}\dots p_{m}^{c_{m}}$ ,其中 $c_{i}$ 都是正整数， $p_{i}$ 都是素数且从小到大。
分解质因子也可以用试除法。求 n 的质因子：

求最小质因子p1。逐个检查从2到 $\sqrt{ n }$ 的所有素数，如果它能整除 n，就是最小质因子。然后连续用 $p_{1}$ 除 n，目的是去掉 n 中的 $p_{1}$ ,得到 $n_{1}$ 。
再找 $n_{1}$ 的最小质因子。逐个检查从 $p_{1}$ 到 $\sqrt{ n_{1} }$ 的所有素数。从 $p_{1}$ 开始试除，是因为 $n_{1}$ 没有比 $p_{1}$ 小的素因子，而且 $n_{1}$ 的因子也是 n 的因子。
继续以上步骤，直到找到所有质因子。
我们直接看一个例题：
【题目描述】
求出区间[a,b]中所有整数的质因数分解。
【输入描述】
输入一行，包含 2 个整数 a，b。2<=a<=b<=10000
【输出描述】
每行输出一个数的分解，形如 k=a1×a2×a3×…，k 从小到大，a 从小到大。
输入：

3 10

输出：

3=3
4=2×2
5=5
6=2×3
7=7
8=2×2×2
9=3×3
10=2×5

直接对每个数进行分解，然后打印出它的因数。

#include <bits/stdc++.h>
using namespace std;
int p[20];  //p[]记录因子，p[1]是最小因子。一个int数的质因子最多有10几个
int c[40];  //c[i]记录第i个因子的个数。一个因子的个数最多有30几个
int factor(int n)
{
    int m = 0;
    for(int i = 2; i <= sqrt(n); i ++)
        if(n % i == 0){
            p[++m] = i, c[m] = 0;
            while(n % i == 0)         //把n中重复的因子去掉
                n/=i, c[m]++;
        }
    if(n > 1)                           //没有被除尽，是素数
        p[++m] = n, c[m] = 1;
    return m;                         //共m个因子
}
int main(){
    int a, b;   cin >> a >> b;
    for(int i = a; i <= b; i ++)
    {
        int m = factor(i);
        cout << i << "=";
        for(int j = 1; j <= m; j ++)  //第j个因子
        { 
            for(int k = 1; k <= c[j]; k ++)//第j个因子的个数
            {    
                cout << p[j];
                if(k < c[j]) 
	                cout << "*";
            }
            if(j < m) 
	            cout << "*";
        }
        cout << endl;
    }
    return 0;
}