徐州有哪些网站制作公司,青岛模板网站建设价格,如何注册网站免费的,wordpress增加管理员寻找整数
【题目描述】 有一个不超过 1 0 1 7 10^17 1017的正整数n#xff0c;知道这个数除以2至49后的余数如下表所示#xff0c;求这个正整数最小是多少
解法一#xff1a;模拟
暴力法#xff1a;一个个检验 1 … 1 0 17 1\dots 10^{17} 1…1017的每个数 由于这个数n…寻找整数
【题目描述】 有一个不超过 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的数有3579…此时步长k2继续满足第二个条件除以3余2的数只能从上一步骤的3579…中找有51117…此时步长k6 为什么k6 因为LCMk(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 n12a113b12 n 2 2 a 2 1 3 b 2 2 n_{2}2a_{2}1 3b_{2}2 n22a213b22 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 ) kn_{2}-n_{1}2(a_{2}-a_{1})3(b_{2}-b_{1}) kn2−n12(a2−a1)3(b2−b1) k是2的倍数 也是3的倍数那么k是2和3的最小公倍数klcm(23)6 3. 继续满足第三个条件除以4余1的数只能从51117…中找有51729…此时步长klcm(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个数的解kk / __gcd(k(long long)i)*i;//连续做LCMbreak;}else {ans k; //累加新的步长}}}coutansendl;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 cmathbool 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的最小公倍数先分解因子:62x377x182x2x2它们的最小公倍数是3x7x2x2x2。
大于1的两个相邻整数互质它们没有公共的质因数。如果题目是任选二个数最大的最小公倍数是N*(N-1)
对于连续的三个整数分两种情况:
N是奇数。 N、N-1、N-2是奇偶奇结论是这三个数两两互质三个数的乘积就是最大的最小公倍数。三个数两两互质也就是说任意一个质数只在N、N-1、N-2中出现一次。 逐个分析质数因子: 质因数2只在N-1中出现 质因数3如果在N中出现(设N3a)就不会在N-1中出现(这要求N-13b无解)也不会在N-2中出现(这要求N-23b无解) 推广到任何一个质数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、345678910111213…n} 操作步骤
输出最小的素数 2筛掉 2 的倍数得{2345678910111213…}输出最小的素数 3筛掉 3 的倍数得{2345678910111213…}输出最小的素数 5筛掉 5 的倍数得{2345678910111213…}继续以上步骤直到队列为空。
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的质数以及质数的个数。 【输入描述】 一个正整数 Nn1000 【输出描述】 两行第 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 np_{1}^{c_{1}}p_{2}^{c_{2}}p_{3}^{c_{3}}\dots p_{m}^{c_{m}} np1c1p2c2p3c3…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 个整数 ab。2ab10000 【输出描述】 每行输出一个数的分解形如 ka1×a2×a3×…k 从小到大a 从小到大。 输入
3 10输出
33
42×2
55
62×3
77
82×2×2
93×3
102×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;
}
