JZOJ 1845——约数

2024-01-30 11:32

文章标签 约数 jzoj 1845

本文主要是介绍JZOJ 1845——约数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这里写图片描述

先将1~n所有非素数除1外的最小公因数求出来
最后循环求出加上每一个i的除1外的最小公约数，如果为0，则加本身

代码如下:

varn,i,j:longint;ans:int64;w:array[2..10000000] of longint;beginreadln(n);for i:=2 to trunc(sqrt(n)) doif w[i]=0 then for j:=1 to n div i do if w[i*j]=0 then w[i*j]:=i;for i:=2 to n do if w[i]>0 then ans:=ans+w[i] else ans:=ans+i;writeln(ans);
end.

这篇关于JZOJ 1845——约数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

http://www.chinasem.cn/article/660102。 23002807@qq.com

Jzoj 条件循环（while，do while）部分代码（共25题）

1020: 【入门】编程求1+3+5+...+n #include <bits/stdc++.h>using namespace std;int n, sum;int main() {scanf("%d", &n);for(int i=1; i<=n; i+=2){sum+=i;} printf("%d", sum);return 0;} 1012: 【入门】两数比大小 #i

Jzoj 二维数组部分代码（共13题）

2788: 【入门】二维数组的输入输出边输入边输出 #include <bits/stdc++.h>using namespace std;int n, m, a[11][11];int main(){scanf("%d %d", &n, &m);//边输入边输出for(int i=1; i<=n; ++i){for(int j=1; j<=m; ++j){scanf("%d", &

《算法竞赛进阶指南》0x32_2约数

定义 ∀ a , b ∈ N , 若 g c d ( a , b ) = 1 , 则称 a ， b 互质 \forall a,b \in \mathbb{N},若gcd(a,b)=1,则称a，b互质 ∀a,b∈N,若gcd(a,b)=1,则称a，b互质。对于三个数或更多个数的情况，我们把 g c d ( a , b , c ) = 1 gcd(a,b,c)=1 gcd(a,b,c)=1的情况称

约数个数a

给定 nn 个正整数 aiai，请你输出这些数的乘积的约数个数，答案对 109+7109+7 取模。输入格式第一行包含整数 nn。接下来 nn 行，每行包含一个整数 aiai。输出格式输出一个整数，表示所给正整数的乘积的约数个数，答案需对 109+7109+7 取模。数据范围 1≤n≤1001≤n≤100, 1≤ai≤2×1091≤ai≤2×109 输入样例： 32

Light OJ 1054 Efficient Pseudo Code 求n^m的约数和

题目来源：Light OJ 1054 Efficient Pseudo Code 题意：求n的m次这个数的所有的约数和思路：首先对于一个数n = p1^a1*p2^a2*p3^a3*…*pk^ak 约束和s = (p1^0+p1^1+p1^2+…p1^a1)(p2^0+p2^1+p2^2+…p2^a2)…(pk^0+pk^1+pk^2+…pk^ak）然后就是先求素数表分解因子然后求

poj-1845 Sumdiv nyoj - 928 小M的因子和

题意：求解A^B的因子和 mod 9901 先求解素因子，然后二分求解等比数列 #include<cstdio>#include<cmath>typedef long long LL;const LL mod = 9901 ;LL pow(LL a,LL b){LL res=1;while(b){if(b&1) res=(res*a)%mod;a=(a*a)%mod;b>>=1;

poj 3361 Gaussian Prime Factors 高斯素数约数

poj 3361 Gaussian Prime Factors 题意：在复数 a+bj (a,b为整数)范围内，约数只有 1, -1, a+bj, -(a+bj)的称为高斯素数。求任给正整数N的所有素因子(|b|>a>0)。默认N<2e9 解法：定理有云： n≡3(mod 4)者，无因式分解。 n≡1(mod 4)者，可唯一分解为两个共轭高斯整数乘积。当然做的时候并不知道！

bzoj1968[Ahoi2005] COMMON 约数研究

题目链接：bzoj1968 题目大意：求1到n各个数约数个数的和。 1≤n≤106 1≤n≤10^6 题解： …我怎么这么蠢。一直在想怎么化这个公式： ∑i=1n∑d|n1 \sum_{i=1}^{n}\sum_{d|n}1 ？？？我真搞笑直接for一遍 n n就好了。对于一个数ii，1到 n n中就会有n/in/i个数是它的倍数，即有

约数倍数

#include<stdio.h> main() { int m,n,k,temp,p; scanf("%d%d",&m,&n); if(m<n) { temp=m; m=n; n=temp; } k=m%n; p=m*n; while(k!=0) { m=n; n=k; k=m%n; }

数论学习之约数

最近学数论真的感觉自己脑子很不好用啊，一个证明题想半天。感觉一些基础的知识还是比较重要的，所以就记录下来吧，加深一下印象。对于一个整数n，假如我们想求到这个整数的所有的约数的话，我们只要对其 1 − n 1-\sqrt{n} 1−n 之间找可以被n整除的那些数，然后就可以找到它们的约数了。时间复杂度 O ( n ) O(\sqrt{n}) O(n ). 代码： //试除法int

JZOJ 1845——约数

相关文章