搜索结果
查询Tags标签： 质数，共有 187条记录-
联合省选 2022 解题报告
D1T1 preprocessor 直接模拟。 D1T2 tree 极差不超过 \(K\)，考虑计算树上路径选值中最小值为 \(v\) 的方案： 将所有 \([l_i,r_i]\) 对 \([v,v+k]\) 取交后的答案减去 对 \([v+1,v+k]\) 取交的答案即可。 容易编一个树形 dp 做到 \(O(nr)\)，拿到 40pts。 考虑值域很大的…
2022/4/27 23:13:43 人评论 次浏览 -
卡牌
题意： 现在有 \(m\) 轮游戏，第 \(i\) 轮游戏会给出 \(c_i\) 个质数，小 A 需要选择任意多张卡牌，使得这些卡牌上面的正整数的乘积能被该轮游戏给出的每个质数整除。 问有多少种卡牌的选法。 暴力容斥 考虑 \(s_i \leq 30\) 时的做法。 目标：使每个质数被整除的方案数，…
2022/4/24 23:15:02 人评论 次浏览 -
【链表+dfs】【脑洞大开--质数只用2 3】 CF #766 (Div. 2), problem: (C) Not Assigning
Problem - 1627C - Codeforces题意：一个n个节点的数， 给出 n-1 条边， 要求给每一条边赋值，使其满足：任意一条边或相连的两条边之和都是质数题解： 这种情况，只有2和其它质数相加也是质数，这种题还是比较多， 能较容易想到。其次，题目没说所用的数不能重复， 索性…
2022/4/24 23:15:00 人评论 次浏览 -
刷题小结
关于质数： 循环遍历：static boolean f(int n) {if (n == 2) {return true;}for (int i = 2; i <= n / i; i++) {if (n % i == 0) {return false;}}return true;}其中的for循环的i <= n / i是i < n的优化 减少了判断的次数，时间优化
2022/4/20 23:12:36 人评论 次浏览 -
质因数（素因数）分解（Java实现）
质因数（素因数）分解（Java实现） 算术基本定理（唯一分解定理） 每个大于1的自然数，要么本身就是质数，要么可以写为2个或以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。代码实现（Java） import java.util.ArrayList; import java.util.List;/***…
2022/4/10 20:12:31 人评论 次浏览 -
算法：质数判断
质数判断方法 一、暴力法 定义：一个只能被1和自身整除的数为质数 算法：从2开始遍历至数字本身减一，若可被其他数整除则不是质数点击查看代码 def isPrime(x):if x==1:return Falsefor i in range(2,x):if not x%i:return Falsereturn True二、遍历优化 特点：任意一个非…
2022/4/5 22:19:08 人评论 次浏览 -
E.判决素数个数（by hszxoj）
题目描述输入两个整数X和Y，输出两者之间的素数个数（包括X和Y）。输入格式两个整数X和Y（1 ≤ X,Y ≤ 10^5）。输出格式输出一个整数，表示X，Y之间的素数个数（包括X和Y）。样例样例输入 1 100 样例输出 25 题意总结 求X与Y之间的素数（质数）个数。 解题思路 使用嵌套循…
2022/4/3 23:24:24 人评论 次浏览 -
44:第n小的质数
44:第n小的质数 描述 输入一个正整数n，求第n小的质数。 输入 一个不超过10000的正整数n。 输出 第n小的质数。 样例输入10样例输出29题意总结 找出第n小的质数（只有1和它本身两个因数）。 解题思路 先从二开始循环到一百万，从二开始在判断是不是质数，如果是就从0开始+…
2022/4/3 23:23:49 人评论 次浏览 -
Min_25 Sieve 学习笔记
这个东西不是人想的。 解决问题：积性函数前缀和。 适用条件：可以快速计算 \(f(p)\) 的前缀和，\(f(p^k)\) 可以被表示成若干完全积性函数的线性组合（指对应项可以快速组合出来）。 时空复杂度：就当是 \(O(\dfrac{n^\frac{3}{4}}{\log n}+n^{1-\epsilon})-O(\sqrt n)\)…
2022/4/3 23:20:40 人评论 次浏览 -
RSA加密原理解释
因数： 16=6 23=6 那么1,6,2,3都是因数 质数： 只能被1和它本身整除的数 余数： 就是python里的%求余（或者说取模运算） 非对称加密 公钥（7,33） (E,N) 7=E,33=N 运算公式：明文的E次方%N=密文 元数据：C,A,O 这里用数字代替 十进制：3,1,15 运算一下，就是3的7次方，1的…
2022/3/28 23:56:06 人评论 次浏览 -
质数、约数（数学知识）
一、试除法判定质数bool prime(int x) {if (x<2)return false;for (int i=2; i<x/i; i++)if (x%i==0)return false;return true; }二、分解质因数void divide(int x) {for (int i=2; i<=x/i; i++)if (x%i==0){int s=0;while (x%i==0)x/=i,s++;cout<<i<&…
2022/3/27 6:23:02 人评论 次浏览 -
算法第一次作业（递归）
A Fibonacci题目描述 定义一个数列f(i) = f(i-1)+f(i-2), f(0) = 0, f(1) = 1. 求f(n) mod (1e9+7) 输入数据 一个正整数n，n<=1e5 输出数据 f(n) mod (1e9+7)标准斐波那契问题，可以递归可以循环；可以数组保存可以直接变量保存 使用递归会超时 注意mod(1e9). 为什么…
2022/3/20 22:27:46 人评论 次浏览 -
质数筛与欧拉函数
第一课时 复习及引入 质数判断 bool isPrime(int x){if(x<2) return false;for(int i=2;i*i<=x;i++){if(x%i==0) return false;}return true; }复杂度分析 \(O(\sqrt{n})\) 引入问题，输入n(\(1\leq n\leq10^6\))个数字(\(0\leq x \leq 10^6\))，判断每个数是不是质…
2022/3/8 23:16:30 人评论 次浏览 -
UOJ188口胡
我们先枚举一个最大质因子，然后设 \(dp[n][k]\) 为 \(n\) 以内使用了 \(pri[k]\) 以内的质数的数的最大质因子之和，答案就是： \[\sum_{k\leq n}dp[\lfloor\frac{n}{pri[k]}\rfloor][k-1] \]当 \(pri[k]\) 大于 \(\sqrt{n}\) 时，后面相当于变成 \(\sqrt{n}\) 以内所有数…
2022/3/7 23:18:31 人评论 次浏览 -
acwing数论笔记
筛法求质数时间复杂度 质数定理:1-n中有n/(lnn)个质数 线性筛
2022/2/23 6:23:42 人评论 次浏览
