2022牛客寒假算法基础集训营4

比赛链接

2022牛客寒假算法基础集训营4

J.区间合数的最小公倍数

题目描述

给定一个区间 \([l,r]\),求其中所有合数的最小公倍数

输入描述:

两个正整数 \(l\)\(r\) ,用空格隔开。

数据范围:\(1\leq l \leq r \leq 30000\)

输出描述:

若区间 \([l,r]\) 中没有任何合数,则输出\(-1\)
否则输出区间 \([l,r]\) 所有合数的最小公倍数,答案对\(1000000007\)取模。

示例1

输入

2 3

输出

-1

说明

区间 \([2,3]\) 的两个数 \(2\)\(3\) 都是素数,不是合数。

示例2

输入

4 6

输出

12

说明

区间\([4,6]\)中有三个数:\(4、5、6\),其中 \(5\) 是素数, \(4\)\(6\) 是合数,它们的最小公倍数是\(12\)

示例3

输入

25000 30000

输出

187554966

解题思路

数学:求取多个数的最小公倍数,即将所有数分解质因数,统计每个素数出现的最高次幂,其乘积即为所求
例:\(a=2^3*3^5*5^1,b=2^4*3^1*5^2\),那么它们的最小公倍数就是 \(2^4*3^5*5^2\)

直接欧拉筛求素数,剩余的合数求最小公倍数即可

  • 时间复杂度:\(O(nlogn)\)

代码

// Problem: 区间合数的最小公倍数
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/23479/J
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// %%%Skyqwq
#include <bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
 
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
 
template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N=3e4+5,mod=1e9+7;
bool st[N];
int prime[N],v[N];
int l,r,m;
void primes(int n)
{
	memset(v,0,sizeof v);
	for(int i=2;i<=n;i++)
	{
		if(v[i]==0)
		{
			prime[++m]=i;
			v[i]=i;
			st[i]=true;
		}
		for(int j=1;j<=m;j++)
		{
			if(i*prime[j]>n||v[i]<prime[j])break;
			v[i*prime[j]]=prime[j];
		}
	}
}
int ksm(int a,int b,int p)
{
	int res=1;
	for(;b;b>>=1)
	{
		if(b&1)res=1ll*res*a%p;
		a=1ll*a*a%p;
	}
	return res;
}
int main()
{
	primes(N);	
    scanf("%d%d",&l,&r);
    int res=1;
    unordered_map<int,int> mp;
    for(int i=l;i<=r;i++)
    {
    	if(!st[i])
    	{
    		int j=i;
    		for(int k=2;k*k<=j;k++)
    		{
    			if(j%k==0)
    			{
    				int t=0;
    				while(j%k==0)t++,j/=k;
    				mp[k]=max(mp[k],t);
    			}
    		}
    		if(j>1)mp[j]=max(mp[j],1);
    	}
    }
    for(auto [x,y]:mp)res=1ll*res*ksm(x,y,mod)%mod;
    printf("%d",res==1?-1:res);
    return 0;
}

推荐这些文章:

牛客寒假算法基础集训营

第一场
F 中位数切分
题目

样例

思路以及证明
因为整个数列中的数只有两种情况,即大于等于m和小于m两种情况,所以可以直接将原来的数列抽象成01串的形式,我们大于等于m的数为1,小于m的数为0。
又因为我们现在要让1处于中间位置,那么我们很容易得出:假设存在某个区间满足题设,若想要这个区间使用的1数量最少,那么总是存在这样一种情况即1的数量比0的数量多1个。
由此我们可以推出,假设存在K个满足条件的区间,其中K越大越好,那么一定有每个区间的1数量比0数量多一个。由此得出,区间的数量就是1的数量-0的数量,即K = cnt1 -cnt0。
假设1比0要少,显然无法存在这样的区间,那么就输...

牛客寒假算法基础集训营6 G 迷宫2(01bfs)

迷宫2
题目大意:
最小化修改的格子的数量,使得人物能从左上角走到右下角
思路:
在每一个位置上有改与不改两种选择,也就是 0 和 1 两种花费,要是花费最少,我们可以使用 01bfs 解决。
01bfs 本质上就是贪心的思想,运用双端队列,将花费为 0 的从队首加入,花费为 1 的从队尾加入,这样每次出队的节点都是当前这一步的最优节点。
在本题中需要记录更改的路径,因为每个节点只会被更新一次,那么我们记录其前驱节点,即可从终点逆推回去。
Code:
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
...

2022牛客寒假算法基础集训营1

A
https://ac.nowcoder.com/acm/contest/23106/A
和的数根=数根的和,因此每个人的权值等价于权值的数根。
设f[i][j]表示前i个人凑出j的方案数,直接根据意义转移即可。
代码:

#include<bits/stdc++.h>
using namespace std;
const int mo=998244353;
int a[1000010],b[1000010],s[1000010];
int cal(int x)
{
while (x>=10)
{
int y=x,z=0;
while (y)
{
z...

2021牛客寒假算法基础集训营1

比赛链接

I.限制不互素对的排列
题目描述
输入一个数 \(n\) ,请构造一个长度为 \(n\) 的排列,使得其中正好有 \(k\) 对相邻的数gcd(最大公约数)大于 1 。 排列是指 1 到 \(n\) 一共 \(n\) 个数,每个数都出现过且仅出现过 1 次。例如, \(\{1,3,2,5,4\}\) 是一个排列,而 \(\{1,3,4,5,3\}\) 、 \(\{1,2,4\}\) 则不是排列
输入描述:
两个整数 \(n\) 和 \(k\), 用空格隔开。
\(2 \leq n \leq 100000,0 \leq k \leq n / 2\)
输出描述:
如果不存在可行的构造...

2021牛客寒假算法基础集训营3

比赛链接
2021牛客寒假算法基础集训营3
C.重力坠击
题目描述
在一个二维平面上有 \(n\) 个敌人,第 \(i\) 个敌人可以描述为一个以 \(\left(x_{i}, y_{i}\right)\) 为圆心, \(r_{i}\) 为半径的圆。
你每次可以对一个半径为 \(R\) 的圆范围内进行攻击(圆心自选,但圆心的横纵坐标必须为整数),对于与你攻击范围有 交点的敌人都会被消火。
你总共可以发动 \(k\) 次攻击,问最多能消多少敌人。
输入描述:
第一行以空格分隔的三个整数 \(n, k, R\) 。
接下来 \(n\) 行每行以空格分隔的三个整数 \(x_{i}, y_{i}, ...

2021牛客寒假算法基础集训营5

题目链接
2021牛客寒假算法基础集训营5
A.美丽的路径
题目描述
叶妺妺非常喜欢图论题,这天她出了一个图论题,有一个 \(n\) 个点 \(m\) 条边的无向图,其中第 \(i\) 个点的点权为 \(a_{i}\) ,她定义一 条点数为 \(k\) 路径: \(b_{1}, b_{2} , \ldots, b_{k}\) ;其中点 \(b_{i-1}\) 与点 \(b_{i}\) 通过一条边直接相连 \((2 \leq i \leq k)\) ,所以路径中可以出现重复 的点。她将一条路径的美丽值定义为:假设这条路径的点数为 \(k\) ,那么这条路径的美丽值就是此路径上的所有点的点 权中...

《2022牛客寒假算法基础集训营1》

A:假设一个三位数为x1y1z1,有cal(x1y1z1) + cal(x2y2z2) = cal((x1 + x2)(y1 + y2) (z1 + z2))
证明:
我们不进位把每一位看成一个多进制数(实际上和十进制是一样的).
可以得出cal(x1y1z1) = cal(x1 + y1 + z1)。cal(x2y2z2)  = cal(x2 + y2 + z2)
 cal((x1 + x2)(y1 + y2) (z1 + z2)) = cal(x1 + x2 + y1 + y2 + z1 + z2).
假设当前都到了最下面一层,则有cal(x1 + y1 + z1) ...

牛客寒假算法基础集训营4 B 进制(线段树)

进制
题目大意:
给出一个数字串,q 次以下两种操作:

输入 1 x y,修改第 x 个字符为 y
输出 2 x y ,代表查询区间 [x,y] 子串所能表示的某进制的最小值,对 1e9+7 取模。

思路:
要得到最小值,显然进制的选择是区间最大值+1。
看操作是单点修改和区间查询,我们考虑用线段树来维护区间上 2-10 进制的值以及区间最大值。
考虑怎样进行区间合并:
假设当前是十进制
14352
/ \
143 53

\[14352 = 143 * 10^2 + 53
\]可以发现区间 k 进制的合并是由 k 进制下 左孩子节点 * k 进制的右孩子节点...

2022牛客寒假算法基础集训营3

比赛链接
2022牛客寒假算法基础集训营3
I.智乃的密码
题目描述
智乃去注册账号,他发现网站的的密码必须符合以下几个条件

密码是仅包含大小写英文字母、数字、特殊符号的字符串。
密码的长度不少于\({L}\)个字符,并且不多于\({R}\)个字符。
密码中应该至少包括①大写英文字母、②小写英文字母、③数字、④特殊符号这四类字符中的三种。
所谓特殊字符,是指非大小写字母、数字以及空格回车等不可见字符的可见字符,包括但不限于"~!@#$%^&*()_+"。

现在智乃有一个长度大小为\({N}\)的字符串\({S}\),她想知道{S}S串中有多少个子串是一个符合条件的密码,请你帮助智...

2022牛客寒假算法基础集训营1 ACDEFHIJL

很久没做题,赛时A了9道加起来WA了16发...剩下三道待补
A. 九小时九个人九扇门
链接:https://ac.nowcoder.com/acm/contest/23106/A
来源:牛客网
题目描述
在打越钢太郎的著名解谜游戏系列《极限脱出》的第一作《九小时九个人九扇门》中,有这样一个有趣的设定:游戏中,99位主人公被困在一座大型的豪华巨轮中,每个人手上都有一个奇怪的手表,手表上有一个数字,99个人的数字分别是1−91−9;在巨轮中,还有很多紧闭的数字门,每扇数字门上也有一个1−91−9的数字,要想打开数字门逃出生天,主角们必须要满足一个奇怪的条件:
kk个人能够打开门上数字为dd的一...

文章标题:2022牛客寒假算法基础集训营4
文章链接:https://www.dianjilingqu.com/50925.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>