寻找整数
【题目描述】
有一个不超过 1 0 1 7 10^17 1017的正整数n,知道这个数除以2至49后的余数如下表所示,求这个正整数最小是多少
解法一:模拟
暴力法:一个个检验 1 … 1 0 17 1\dots 10^{17} 1…1017的每个数
由于这个数n最大可能是 1 0 17 10^{17} 1017,验证的时间太长
解法二: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_{1} n1和 n 2 n_{2} n2满足
n 1 = 2 a 1 + 1 = 3 b 1 + 2 n_{1}= 2a_{1}+1 = 3b_{1}+2 n1=2a1+1=3b1+2
n 2 = 2 a 2 + 1 = 3 b 2 + 2 n_{2}=2a_{2}+1= 3b_{2}+2 n2=2a2+1=3b2+2
n 2 n_{2} n2和 n 1 n_{1} n1的差 k = n 2 − n 1 = 2 ( a 2 − a 1 ) = 3 ( b 2 − b 1 ) k=n_{2}-n_{1}=2(a_{2}-a_{1})=3(b_{2}-b_{1}) k=n2−n1=2(a2−a1)=3(b2−b1)
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;//连续做LCMbreak;}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到 n \sqrt{ n } n。证明:若 n = a x b, 设 a≤ n \sqrt{ n } 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;elsestd::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";elsecout << "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没有因数3ans = n * (n - 1) * (n - 3); else //n有因数3ans = (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 行一个整数,表示素数个数。
输入:
10
输出:
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 … p m c m n=p_{1}^{c_{1}}p_{2}^{c_{2}}p_{3}^{c_{3}}\dots p_{m}^{c_{m}} n=p1c1p2c2p3c3…pmcm,其中 c i c_{i} ci都是正整数, p i p_{i} pi都是素数且从小到大。
分解质因子也可以用试除法。求 n 的质因子:
- 求最小质因子p1。逐个检查从2到 n \sqrt{ n } n 的所有素数,如果它能整除 n,就是最小质因子。然后连续用 p 1 p_{1} p1除 n,目的是去掉 n 中的 p 1 p_{1} p1,得到 n 1 n_{1} n1。
- 再找 n 1 n_{1} n1的最小质因子。逐个检查从 p 1 p_{1} p1 到 n 1 \sqrt{ n_{1} } n1 的所有素数。从 p 1 p_{1} p1开始试除, 是因为 n 1 n_{1} n1没有比 p 1 p_{1} p1小的素因子,而且 n 1 n_{1} n1的因子也是 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;
}