lb开金矿 QDUOJ 数论
2024-10-07 06:21:28
lb开金矿 QDUOJ 数论
题意
大家都知道lb有n个小弟(编号从2到n+1),他们可以按照规则传递信息:某天编号为i的小弟收到信息后,那么第二天他会给编号为j的小弟传达信息,其中gcd(i,j)=1(即i,j互质,且j可能不唯一)。现在,lb知道了一个新的钻石矿的信息,lb在第0天的时候告诉了他的第k个小弟(编号为k+1),问几天后他的小弟们都会知道这条消息?
解题思路
这个题看了看输入的数据范围,\(1e14\)的范围,嗯,又看了看样例,回想了一下学长们出题的规律,感觉答案要么是1,要么就是2,但是奈何我不会,后来还是学长讲了一下这个题,让人恍然大悟。
首先,lb通知的第一个小弟会通知和他互素的所有人,这里如果通知的第一个小弟的编号是质数的话,那么好了,他会通知其他所有的小弟,因为质数和其他数都互质,等等,如果有个小弟的编号正好是第一个小弟编号的整数倍的话也是没法通知到的,所以这里需要进行一下特判,判断一下这个质数的2倍是不是超过了n,如果超过了,那么就需要两天,否者就是一天。如果第一个通知的小弟的编号不是质数,那么就需要两天,
代码实现
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
bool judge(ll x)
{
if(x==2) return true;
ll limit=(ll)sqrt(x)+1;
for(ll i=2; i<=limit; i++)
{
if(x%i==0)
return false;
}
return true;
}
int main()
{
ll n, k;
cin>>n>>k;
if(judge(k+1))
{
if((k+1)*2 > n+1)
cout<<1<<endl;
else
cout<<2<<endl;
}
else
{
cout<<2<<endl;
}
return 0;
}
最新文章
- 硬盘安装linux的两条命令
- 为bootstrap添加更多自定义图标
- codevs1230 元素查找
- 发布资源到Asset Store
- WPF 之 线程使用
- win10 enterprise 10240激活:
- ubuntu server修改时区
- oracle sql命令行中上下左右使用
- hdu 1420(Prepared for New Acmer)(中国剩余定理)(降幂法)
- LeetCode &; Q414-Third Maximum Number-Easy
- IDEA代码格式化快捷键(新)
- Spring Boot (七)MyBatis代码自动生成和辅助插件
- log日志文件
- JavaScript 基础(一) - JavaScript的引入方式,JavaScript 变量命名规则,JS 的五种基本数据类型,ECMAScript 算数运算符,逻辑运算符
- Webpack2 中的 NamedModulesPlugin 与 HashedModuleIdsPlugin
- centos7 go ENV 部署
- [CodeForces 892A] Greed (Java中sort实现从大到小排序)
- Ajax的返回状态码(status)
- QNJR-GROUP/EasyTransaction: 依赖于Spring的一个柔性事务实现,包含 TCC事务,补偿事务,基于消息的最终一致性事务,基于消息的最大努力交付事务交付QNJR-GROUP/EasyTransaction: 依赖于Spring的一个柔性事务实现,包含 TCC事务,补偿事务,基于消息的最终一致性事务,基于消息的最大努力交付事务交付
- Java web 调试技巧之查看浏览器中调试中的network
热门文章
- 浅谈Mybatis通用Mapper使用方法_java - JAVA
- 【SaltStack官方版】—— STORING JOB RESULTS IN AN EXTERNAL SYSTEM
- 数据库基本概念及Oracle基本语句
- 【NOIP2016提高A组模拟8.17】(雅礼联考day1)Matrix
- html abbr标签 语法
- linux系统安装Oracle11g详细步骤
- sqli-labs(35)
- [CSP-S模拟测试]:Cicada拿衣服(暴力+乱搞)
- the path component: &#39;/var&#39; is world-writable
- 大数据笔记(三十一)——SparkStreaming详细介绍,开发spark程序