【洛谷】数论题目
目录
P1029 最大公约数和最小公倍数问题
P1403 [AHOI2005]约数研究
P1835 素数密度
P1029 最大公约数和最小公倍数问题
题目链接
本题标签写的是枚举和暴力，傻乎乎的我真的用暴力写，果然连续TLE
尝试从数学的角度简单的分析一下，P和Q的最大公约数是X，由算术基本定理可得，P/X与Q/X互质，且P与Q的最小公倍数为，即
AC代码如下：
X*i = P， X*j = Y
只需判断P能否整除Y且P/X与Q/X互质即可。
#include
using namespace std;const int M = 200010;int gcd(int a,int b){return b?gcd(b,a%b):a;
}int main()
{int x, y, res = 0;cin>>x>>y;for(int i=1;i<=(y/x);i++)if(y%(i*x)==0 && gcd(y/(i*x),i)==1)res++;cout< P1403 [AHOI2005]约数研究
题目链接
用倍数法求每个数的正约数即可。
#include
using namespace std;int div(int n)
{int sum = 0;for(int i=1;i<=n;i++)for(int j=1;j<=n/i;j++)sum ++;return sum;
}int main()
{int n;cin>>n;cout< P1835 素数密度
题目链接
代码如下：
L,R的范围很大，任何已知算法都无法在规定时间内生成[1,R]中所有的质数，但是R-L的值很小，并且任何一个合数n必定包含一个不超过sqrt(n)的质因子。
用筛法求出2~sqrt(R)之间的所有质数。对于每个质数p，把[L,R]中能被p整除的数标记，标记的数为合数。
#include
#include
#include
using namespace std;typedef long long ll;//数据达到21亿了(2e31-1)，但是区间较小
const int MAX_N = 50010; int d[1000010]; //定义一个区间表示L~R之间的数是否为质数，0质数，1表示合数
int v[MAX_N], prime[MAX_N];
int m = 0; //质数数量void primes(int n)
{memset(v,0,sizeof(v)); //存放每个数的最小质因子for(int i=2;i<=n;i++){if(v[i]==0) { v[i] = i; prime[++m] = i; }//给当前的数i乘上一个质因子for(int j=1;j<=m;j++){//i有比prime[j]更小的质因子，或者超出n的范围，停止循环if(prime[i]>v[i] || prime[j]>n/i) break;v[i*prime[j]] = prime[j];}}
}int main()
{int L,R;cin>>L>>R;primes(50000);int res = 0;for(int i=1;i<=m;i++){if(prime[i]>R) break; //当L和R元素较小时，减少操作ll z = ceil(1.0*L/prime[i]); //上取整ll q = max(z,2ll); while(q<=ceil(1.0*R/prime[i])) //上取整d[(q++)*prime[i] - L + 1] = 1;}for(int i=1;i<=R-L+1;i++)if(d[i]==0) res++;cout<
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！