当前位置: 首页 > news >正文

2023 牛客国庆day4 【10.2训练补题】

 

目录

B-Basic Gcd Problem(素数筛+快速幂)

H-Harder Gcd Problem(素数)


 B-Basic Gcd Problem(素数筛+快速幂)

打表找规律发现答案为 (n质因子数目)^c 

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
const int inf=1<<30;
const ll mod=1e9+7;
inline void read(ll &x){ll f=1;x=0;char ch=getchar();while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}x*=f;
}
ll T,n,c;
int ct[N];
int su[N],cnt;
bool u[N];
void init(){memset(u,true,sizeof(u));cnt=0;for(int i=2;i<N;i++){if(u[i])su[++cnt]=i,ct[i]=1;for(int j=1;j<=cnt&&su[j]*i<N;j++){u[su[j]*i]=0;ct[su[j]*i]=ct[i]+1;//printf("ct[%d]%d\n",su[i]*j,ct[su[i]*j]);if(i%su[j]==0)break;}}
}
ll quickp(ll b,ll p){ll res=1;while(p){if(p&1)res=res*b%mod;p>>=1;b=b*b%mod;}return res;
}
int main(){init();read(T);while(T--){read(n);read(c);printf("%lld\n",quickp(c,ct[n]));}return 0;
} 

 

H-Harder Gcd Problem(素数)

参考题解:

【2020年牛客暑假第四场】H题 Harder Gcd Problem_2020牛客第四场 h题-CSDN博客

*所有数字都可由素数与其他数字相乘得到

*注意 v[ i ]标记时机

*偶数是素数2的倍数无需特判

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;
const int inf=1<<30;
const ll mod=1e9+7;
inline void read(int &x){int f=1;x=0;char ch=getchar();while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch&15);ch=getchar();}x*=f;
}
int T,n;
int v[N];int su[N],cnt;
bool u[N];
void init(){memset(u,true,sizeof(u));for(int i=2;i<N;i++){if(u[i])su[++cnt]=i;for(int j=1;j<=cnt&&su[j]*i<N;j++){u[su[j]*i]=0;if(i%su[j]==0)break;}}
}vector<pi>res;
vector<int>tmp;
int main(){read(T);init();while(T--){read(n);for(int i=2;i<=n;i++)v[i]=1;int ani;for(int i=1;su[i]*2<=n;i++)ani=i;for(int i=ani;i>0;i--){tmp.clear();for(int j=1;j*su[i]<=n;j++){int t=j*su[i];if(v[t]){tmp.push_back(t);}}int sz=tmp.size();if(sz&1){swap(tmp[1],tmp[sz-1]);}for(int j=0;j+1<sz;j+=2){res.push_back({tmp[j],tmp[j+1]});v[tmp[j]]=v[tmp[j+1]]=0;}}printf("%d\n",res.size());for(auto i:res)printf("%d %d\n",i.first,i.second);res.clear();}return 0;
}

相关文章:

2023 牛客国庆day4 【10.2训练补题】

目录 B-Basic Gcd Problem&#xff08;素数筛快速幂&#xff09; H-Harder Gcd Problem&#xff08;素数&#xff09; B-Basic Gcd Problem&#xff08;素数筛快速幂&#xff09; 打表找规律发现答案为 (n质因子数目)^c #include<bits/stdc.h> using namespace std;…...

android的USB开发时 mUsbManager.getDeviceList()获取都为空

类提供的主要方法有&#xff1a; getDeviceList() 获得设备列表&#xff0c;返回的是一个HashMap.;hasPermission(UsbDevice device) 判断你的应用程序是否有接入此USB设备的权限&#xff0c;如果有则返回真&#xff0c;否则返回false.openDevice(UsbDevice device) 打开USB设…...

SpringCloud Alibaba - Seata 部署 TC 服务,并集成微服务

目录 一、Seata 架构 1.1、Seata 架构重要角色 1.2、部署 TC 服务 1.2.1、前言 1.2.2、下载 seata-server 包&#xff0c;解压 1.2.3、修改配置 1.2.4、在 nacos 中添加配置 1.2.5、创建数据库表 1.2.6、启动 TC 服务 1.3、微服务集成 Seata 1.3.1、引入依赖 1.3.2、…...

Java基础面试,接口和抽象类的区别?

接口和抽象类的区别&#xff1f; 抽象类可以存在普通成员函数&#xff0c;而接口中只能存在public abstract 方法。抽象类中的成员变量可以是各种类型的&#xff0c;而接口中的成员变量只能是public static final类型的.抽象类只能继承一个&#xff0c;接口可以实现多个。 接…...

《视觉 SLAM 十四讲》V2 第 4 讲 李群与李代数 【什么样的相机位姿 最符合 当前观测数据】

P71 文章目录 4.1 李群与李代数基础4.1.3 李代数的定义4.1.4 李代数 so(3)4.1.5 李代数 se(3) 4.2 指数与对数映射4.2.1 SO(3)上的指数映射罗德里格斯公式推导 4.2.2 SE(3) 上的指数映射SO(3),SE(3),so(3),se(3)的对应关系 4.3 李代数求导与扰动模型4.3.2 SO(3)上的李代数求导…...

【深蓝学院】手写VIO第4章--基于滑动窗口算法的 VIO 系统:可观性和 一致性--笔记

0. 内容 T1. 参考SLAM14讲P247直接可写&#xff0c;注意 ξ 1 , ξ 2 \xi_1,\xi_2 ξ1​,ξ2​之间有约束&#xff08;关系&#xff09;。 套用舒尔补公式&#xff1a; marg掉 ξ 1 \xi_1 ξ1​之后&#xff0c;信息被传递到 L 1 和 L 2 L_1和L_2 L1​和L2​之间了。 T2....

mfc 动态加载dll库,Mat转CImage,读ini配置文件,鼠标操作,在edit控件上画框,调试信息打印

动态加载dll库 h文件中添加 #include "mydll.h" #ifdef UNICODE //区分字符集 #define LoadLibrary LoadLibraryW #else #define LoadLibrary LoadLibraryA #endif // !UNICODEtypedef double(*mydllPtr)(int, int);类内添加&#xff1a; mydllPtr m_mydll; cpp…...

索尼 toio™应用创意开发征文|检测工业平台震动

虽然索尼toio Q宝机器人主要是为儿童教育娱乐开发的&#xff0c;但我认为它在工业等领域也有一定应用潜力。例如&#xff0c;工业领域经常会有某些平面在实际作业中持续震动&#xff0c;导致零件过疲劳、平台失去稳定等问题。而这样的平台往往位于机器内部&#xff0c;从外部很…...

【已解决】 Expected linebreaks to be ‘LF‘ but found ‘CRLF‘.

问题描述 团队都是用mac&#xff0c;只有我自己是windows&#xff0c;启动项目一直报错 Expected linebreaks to be ‘LF‘ but found ‘CRLF‘. 但我不能因为自己的问题去改团队配置&#xff0c;也尝试过该vscode配置默认是LF还是报错 思路 看文章vscode如何替换所有文件的…...

Java8 Lambda.stream.sorted() 方法使用浅析分享

文章目录 Java8 Lambda.stream.sorted() 方法使用浅析分享sorted() 重载方法一升序降序 sorted() 重载方法二升序降序多字段排序 mock代码 Java8 Lambda.stream.sorted() 方法使用浅析分享 本文主要分享运用 Java8 中的 Lambda.stream.sorted方法排序的使用&#xff01; sorted…...

Neural Networks for Fingerprint Recognition

Neural Computation ( IF 3.278 ) 摘要&#xff1a; 在采集指纹图像数据库后&#xff0c;设计了一种用于指纹识别的神经网络算法。当给出一对指纹图像时&#xff0c;算法输出两个图像来自同一手指的概率估计值。在一个实验中&#xff0c;神经网络使用几百对图像进行训练&…...

ChatGPT推出全新功能,引发人工智能合成声音担忧|百能云芯

人工智能AI科技企业OpenAI公司25日宣布&#xff0c;其聊天应用程序ChatGPT如今具备「看、听、说」能力&#xff0c;至少能够理解口语、用合成语音回应并且处理图像&#xff1b;但专家忧心&#xff0c;以假乱真与深度伪造的乱象可能变本加厉。 国家广播公司新闻网(NBC News)报导…...

Java 实现遍历一个文件夹,文件夹有100万数据,获取到修改时间在2天之内的数据

目录 1 需求2 实现1&#xff08;第一种方法&#xff09;2 实现2 &#xff08;推荐使用这个&#xff0c;快&#xff09;3 实现3&#xff08;推荐&#xff09; 1 需求 现在有一个文件夹&#xff0c;里面会一直存数据&#xff0c;动态的存数据&#xff0c;之后可能会达到100万&am…...

持续集成部署-k8s-命令行工具:基础命令的使用

持续集成部署-k8s-命令行工具:基础命令的使用 1. 资源类型与别名2. 资源操作2.1 创建对象2.2 显示和查找资源2.3 更新资源2.4 修补资源2.5 编辑资源2.6 scale 资源2.7 删除资源3. 格式化输出1. 资源类型与别名 资源类型缩写别名clusterscomponentstatusescsconfigmapscmdaemon…...

使用python脚本的时间盲注完整步骤

文章目录 一、获取数据库名称长度二、获取数据库名称三、获取表名总长度四、获取表名五、获取指定表列名总长度六、获取指定表列名七、获取指定表指定列的表内数据总长度八、获取指定表指定列的表内数据 一、获取数据库名称长度 测试环境是bwapp靶场 SQL Injection - Blind - …...

C++项目:仿mudou库one thread one loop式并发服务器实现

目录 1.实现目标 2.HTTP服务器 3.Reactor模型 3.1分类 4.功能模块划分: 4.1SERVER模块: 4.2HTTP协议模块: 5.简单的秒级定时任务实现 5.1Linux提供给我们的定时器 5.2时间轮思想&#xff1a; 6.正则库的简单使用 7.通用类型any类型的实现 8.日志宏的实现 9.缓冲区…...

【算法训练-贪心算法 一】买卖股票的最佳时机II

废话不多说&#xff0c;喊一句号子鼓励自己&#xff1a;程序员永不失业&#xff0c;程序员走向架构&#xff01;本篇Blog的主题是【贪心算法】&#xff0c;使用【数组】这个基本的数据结构来实现&#xff0c;这个高频题的站点是&#xff1a;CodeTop&#xff0c;筛选条件为&…...

单阶段目标检测与双阶段目标检测的联系与区别

&#x1f680; 作者 &#xff1a;“码上有钱” &#x1f680; 文章简介 &#xff1a;AI-目标检测算法 &#x1f680; 欢迎小伙伴们 点赞&#x1f44d;、收藏⭐、留言&#x1f4ac;简介 双阶段目标检测算法与单阶段目标检测算法在工作原理和性能方面存在一些相似与差异之处。下…...

Mysql技术文档--设计表规范式-一次性扫盲

阿丹&#xff1a; 在设计表的时候经常出现一些问题&#xff0c;其实自己很清楚就是因为在设计表的时候没有规范。导致后期加表的时候出现了问题。所以趁着这个假期卷一卷。同时只有在开始的时候 几大范式 在关系型数据库中&#xff0c;数据表设计的基本原则、规则就称为范式。…...

python socket 传输opencv读取的图像

python socket网络编程 将ros机器人摄像头捕捉的画面在上位机实时显示&#xff0c;需要用到socket网络编程&#xff0c;提供了TCP和UDP两种方式 TCP服务器端代码: 创建TCP套接字: s socket(AF_INET, SOCK_STREAM) 创建了一个TCP套接字。SOCK_STREAM 表示这是一个TCP套接字&…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

32单片机——基本定时器

STM32F103有众多的定时器&#xff0c;其中包括2个基本定时器&#xff08;TIM6和TIM7&#xff09;、4个通用定时器&#xff08;TIM2~TIM5&#xff09;、2个高级控制定时器&#xff08;TIM1和TIM8&#xff09;&#xff0c;这些定时器彼此完全独立&#xff0c;不共享任何资源 1、定…...

2025-05-08-deepseek本地化部署

title: 2025-05-08-deepseek 本地化部署 tags: 深度学习 程序开发 2025-05-08-deepseek 本地化部署 参考博客 本地部署 DeepSeek&#xff1a;小白也能轻松搞定&#xff01; 如何给本地部署的 DeepSeek 投喂数据&#xff0c;让他更懂你 [实验目的]&#xff1a;理解系统架构与原…...