搜索结果
查询Tags标签： 约数，共有 39条记录-
AcWing 算法基础课 数论
一、质数质数是大于1的自然数，只包含1和本身两个约数。1、质数的判定，O(sqrt(n))试除法，推荐循环i<=n/i（防止溢出和sqrt计算）2、分解质因子，O(logn~sqrt(n))1 for(int i=2;i<=n/i;i++)2 {3 if(n%i==0)4 {//此时2~i-1的质因子已经除完，i必为质数5 …
2022/1/1 20:12:45 人评论 次浏览 -
「51nod1220」 约数之和 题解
Statement \(\sigma(k)\) 表示 \(k\) 的所有约数的和。\(\sigma(6) = 1 + 2 + 3 + 6 = 12\) 定义 \(S(N) = ∑_{i=1}^N ∑_{j=1}^N \sigma(i*j)\) 给出正整数 \(N\)，求 \(S(N)\) ，由于结果可能会很大，输出 $\mod\ \ \ 1000000007(10^9 + 7) $的结果。 Solution \[\begi…
2021/12/19 23:28:39 人评论 次浏览 -
「51nod1220」 约数之和 题解
Statement \(\sigma(k)\) 表示 \(k\) 的所有约数的和。\(\sigma(6) = 1 + 2 + 3 + 6 = 12\) 定义 \(S(N) = ∑_{i=1}^N ∑_{j=1}^N \sigma(i*j)\) 给出正整数 \(N\)，求 \(S(N)\) ，由于结果可能会很大，输出 $\mod\ \ \ 1000000007(10^9 + 7) $的结果。 Solution \[\begi…
2021/12/19 23:28:39 人评论 次浏览 -
【leetcode】3的幂c++
题目描述： 给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。 整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x 示例1：输入：n = 27 输出：true示例2：输入：n = 0 输出：false示例3：输入：n = 9 输出：true示例4：输…
2021/9/28 20:12:34 人评论 次浏览 -
【leetcode】3的幂c++
题目描述： 给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。 整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x 示例1：输入：n = 27 输出：true示例2：输入：n = 0 输出：false示例3：输入：n = 9 输出：true示例4：输…
2021/9/28 20:12:34 人评论 次浏览 -
CF1334E Divisor Paths
这是一道数论题，而不是图论题。 整个思路大概可以分成两步走：构造最短路，最短路计数。当然都是数学方法。 一、构造最短路 有一个我到最后也没猜出来的结论：\(u\) 和 \(v\) 之间的最短路，一定经过 \(\gcd(u,v)\)。 要理解这句话，必须先明白题目里路径长度的含义：\(…
2021/9/6 23:36:05 人评论 次浏览 -
CF1334E Divisor Paths
这是一道数论题，而不是图论题。 整个思路大概可以分成两步走：构造最短路，最短路计数。当然都是数学方法。 一、构造最短路 有一个我到最后也没猜出来的结论：\(u\) 和 \(v\) 之间的最短路，一定经过 \(\gcd(u,v)\)。 要理解这句话，必须先明白题目里路径长度的含义：\(…
2021/9/6 23:36:05 人评论 次浏览 -
CCF 202104-4 校门外的树 Python
202104-4 校门外的树 题目链接题型分析代码但运行超时，只能拿到60分，欢迎各位提问和改进！题目链接 http://118.190.20.162/view.page?gpid=T125 题型分析 典型的DP问题 递推公式： f[i] = f[i] + f[j] *calc(i,j) 含义： aj - ai 表示到i为止的最后一个区间，其长度为…
2021/9/4 17:05:53 人评论 次浏览 -
CCF 202104-4 校门外的树 Python
202104-4 校门外的树 题目链接题型分析代码但运行超时，只能拿到60分，欢迎各位提问和改进！题目链接 http://118.190.20.162/view.page?gpid=T125 题型分析 典型的DP问题 递推公式： f[i] = f[i] + f[j] *calc(i,j) 含义： aj - ai 表示到i为止的最后一个区间，其长度为…
2021/9/4 17:05:53 人评论 次浏览 -
欧几里得算法
欧几里得算法：gcd(x,y)=gcd(y,x%y);边界条件：if（y==0）return x; 证明：我们设gcd(a,b)=d（1），a=k*b+c（2），再令a=k1*d,b=k2*d（3）由（2）得c=a-k*b（4），然后将（1）带入（4）得到:c=k1*d-k*k2*d,即c=(k1-k*k2)*d.这样就说明，a%b有d这个约数，因为开始我们设b也…
2021/8/23 17:35:37 人评论 次浏览 -
欧几里得算法
欧几里得算法：gcd(x,y)=gcd(y,x%y);边界条件：if（y==0）return x; 证明：我们设gcd(a,b)=d（1），a=k*b+c（2），再令a=k1*d,b=k2*d（3）由（2）得c=a-k*b（4），然后将（1）带入（4）得到:c=k1*d-k*k2*d,即c=(k1-k*k2)*d.这样就说明，a%b有d这个约数，因为开始我们设b也…
2021/8/23 17:35:37 人评论 次浏览 -
约数个数定理
int div(int x){int i,s,r;for (i = 2; i * i <= n; i++) {r = 0; //指数while (n % i == 0) { //循环分解质因数r++; //因数的指数n /= i; …
2021/8/6 6:06:43 人评论 次浏览 -
约数个数定理
int div(int x){int i,s,r;for (i = 2; i * i <= n; i++) {r = 0; //指数while (n % i == 0) { //循环分解质因数r++; //因数的指数n /= i; …
2021/8/6 6:06:43 人评论 次浏览 -
蓝桥杯:问 78120 有多少个约数?
求：78120 有多少个约数。首先声明两个变量。利用for 循环和if语句完成代码的书写。 所以，运行下来的结果是24，78120 的约数有24个；
2021/7/18 23:35:02 人评论 次浏览 -
蓝桥杯:问 78120 有多少个约数?
求：78120 有多少个约数。首先声明两个变量。利用for 循环和if语句完成代码的书写。 所以，运行下来的结果是24，78120 的约数有24个；
2021/7/18 23:35:02 人评论 次浏览
