目录

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<iostream>
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<<res;
	return 0;
}

P1403 [AHOI2005]约数研究

题目链接

用倍数法求每个数的正约数即可。

#include<iostream>
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<<div(n);
	return 0;
}

P1835 素数密度

题目链接

代码如下：

L,R的范围很大，任何已知算法都无法在规定时间内生成[1,R]中所有的质数，但是R-L的值很小，并且任何一个合数n必定包含一个不超过sqrt(n)的质因子。

用筛法求出2~sqrt(R)之间的所有质数。对于每个质数p，把[L,R]中能被p整除的数标记，标记的数为合数。

#include<iostream>
#include<cmath>
#include<cstring>
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<<res;
	return 0;
}