F. Vasilije Loves Number Theory

Problem - F - Codeforces

思路:分析一下题意,对于第一种操作来说,每次乘以x,那么n=n*x,然后问是否存在一个a使得gcd(n,a)=1并且n*a的约数个数等于n,有最大公约数等于1我们能够知道其实这两个数是互质的,所以d(n)*d(a)=d(n*a),那么就是要d(a)=n/d(n),所以n%d(n)一定要等于零,同时又因为当取模等于零时我们发现一定可以构造除一种方案,我们先选择一个与n互质的数x,然后让a=x^t,此时a共有(t+1)个约数,所以我们只需要让(t+1)=n/d(n)就能够构造出来,所以现在的问题变成了,我们能够判断n%d(n)等于0,我们知道一个因数个数的公式,就是所有质因数的个数加一的累乘,那么我们只需要维护n的所有质因数的个数即可,同时n并不能够直接乘以x,因为可能会乘的很大,所以我们在求出来d(n)之后,可以看看n与所有的x能否把d(n)消完,如果能消则代表可以

// Problem: F. Vasilije Loves Number Theory
// Contest: Codeforces - Codeforces Round 900 (Div. 3)
// URL: https://codeforces.com/contest/1878/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms#include<bits/stdc++.h>
#include<sstream>
#include<cassert>
#define fi first
#define se second
#define i128 __int128
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> PII;
const double eps=1e-7;
const int N=5e5+7 ,M=5e5+7, INF=0x3f3f3f3f,mod=1e9+7,mod1=998244353;
const long long int llINF=0x3f3f3f3f3f3f3f3f;
inline ll read() {ll x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') {x=(ll)x*10+c-'0';c=getchar();} return x*f;}
inline void write(ll x) {if(x < 0) {putchar('-'); x = -x;}if(x >= 10) write(x / 10);putchar(x % 10 + '0');}
inline void write(ll x,char ch) {write(x);putchar(ch);}
void stin() {freopen("in_put.txt","r",stdin);freopen("my_out_put.txt","w",stdout);}
bool cmp0(int a,int b) {return a>b;}
template<typename T> T gcd(T a,T b) {return b==0?a:gcd(b,a%b);}
template<typename T> T lcm(T a,T b) {return a*b/gcd(a,b);}
void hack() {printf("\n----------------------------------\n");}int T,hackT;
ll n,m,k;
int pr[N],ttcnt;
bool st[N];
int cnt[N];
map<int,int> tcnt;void init() {for(int i=2;i<=1000;i++) {if(!st[i]) pr[ttcnt++]=i;for(int j=0;pr[j]<=1000/i;j++) {st[pr[j]*i]=true;if(i%pr[j]==0) break;}}
}void t_init(int x) {tcnt.clear();for(int i=0;i<ttcnt;i++) cnt[pr[i]]=0;for(int j=0;j<ttcnt;j++) {if(pr[j]>x) break;while(x%pr[j]==0) {cnt[pr[j]]++;x/=pr[j];}}if(x!=1) tcnt[x]++;
}int get() {int res=1;for(int i=0;i<ttcnt;i++) res=res*(cnt[pr[i]]+1);for(auto &it:tcnt) res=res*(it.se+1);return res;
}void change(int x,int &d) {int s=gcd(x,d);d/=s;
}bool check(vector<int> &temp,int d) {change(n,d);for(int i=0;i<temp.size();i++) change(temp[i],d);if(d==1) return true;else return false;
}void solve() {n=read();int q=read();t_init(n);vector<int> temp;while(q--) {int op=read();if(op==1) {int x=read();temp.push_back(x);for(int j=0;j<ttcnt;j++) {if(pr[j]>x) break;while(x%pr[j]==0) {cnt[pr[j]]++;x/=pr[j];}}if(x!=1) tcnt[x]++;if(check(temp,get())) printf("YES\n");else printf("NO\n");}else if(op==2) {t_init(n);temp.clear();}}
}   int main() {init();// stin();// ios::sync_with_stdio(false); scanf("%d",&T);// T=1; while(T--) hackT++,solve();return 0;       
}          

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/154367.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

wireshark抓包分析HTTP协议,HTTP协议执行流程,

「作者主页」&#xff1a;士别三日wyx 「作者简介」&#xff1a;CSDN top100、阿里云博客专家、华为云享专家、网络安全领域优质创作者 「推荐专栏」&#xff1a;对网络安全感兴趣的小伙伴可以关注专栏《网络安全入门到精通》 使用WireShark工具抓取「HTTP协议」的数据包&#…

RedissonClient中Stream流的简单使用

1、pub端 //获取一个流 RStream rStream redissonClient.getStream("testStream"); //创建一个map&#xff0c;添加数据 Map<String, Object> rr new HashMap<>(); rr.put("xx", RandomUtil.randomString(5)); //添加到流 rStream.addAll(r…

Allegro如何查看器件的管脚号?

Allegro在默认情况下,器件是不显示管脚号的。 Allegro默认情况下,器件不显示管脚编号。 在PCB布局时,有时候我们需要看器件的管脚号,然后才能方便布局。那如何查看器件的管脚号呢? 这里介绍两种查看器件的管脚编号的方法。 方法一: (1)选择菜单Display→Color/Visi…

一款好用的PDF文档解密软件

PDF Decrypter pro 纯免费&#xff0c;没有页数限制&#xff0c;没有额外水印&#xff0c;强烈推荐&#xff01;

提升后端API性能的几种解决方案

&#x1f514;目的 提升后端API性能的主要目的是为了提高系统整体的响应速度、并发能力以及可用性。主要原因包括: 提高用户体验 后端API性能好可以减少响应延迟,给用户流畅的体验。 提高系统吞吐量 优化API性能可以提高系统的整体吞吐量,处理更多用户请求。 节省服务器资源…

深入理解强化学习——强化学习和有监督学习

分类目录&#xff1a;《深入理解强化学习》总目录 通过前文的介绍&#xff0c;我们现在应该已经对强化学习的基本数学概念有了一定的了解。这里我们回过头来再看看一般的有监督学习和强化学习的区别。以图片分类为例&#xff0c;有监督学习&#xff08;Supervised Learning&…

利用Python构建自定义报告生成器支持SEO分析实战总结

在进行SEO&#xff08;搜索引擎优化&#xff09;分析时&#xff0c;定制化的报告生成器是非常有价值的工具之一。通过利用Python编程语言构建自定义报告生成器&#xff0c;可以更好地满足个性化的需求&#xff0c;并提供详尽的SEO分析结果。本文将分享一些实践经验&#xff0c;…

3、在 CentOS 8 系统上安装 PostgreSQL 15.4

PostgreSQL&#xff0c;作为一款备受欢迎的开源关系数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;已经存在了三十多年的历史。它提供了SQL语言支持&#xff0c;用于管理数据库和执行CRUD操作&#xff08;创建、读取、更新、删除&#xff09;。 由于其卓越的健壮性…

对比纯软开与嵌入式硬件开发谁更好呢?

对比纯软开与嵌入式硬件开发谁更好呢&#xff1f; 你的纠结和犹豫是理解的&#xff0c;职业选择确实是一个重要的决策。我明白你在嵌入式和软件开发之间犹豫不决的原因。让我给你提供一些建议&#xff0c;帮助你做出更明智的决定。最近很多小伙伴找我&#xff0c;说想要一些嵌入…

MySQL对日期计算

mysql日期计算 前言使用场景一 日期作减法操作二 获取前一天或后一天的日期三 获取前一个月或后一个月的日期四 获取前一年或后一年的日期五 查询一个月内的申请记录 总结 前言 在MySQL中&#xff0c;日期计算是非常常见的操作。其中&#xff0c;日期减法操作可以用来计算两个…

Springboot接收http参数总结(最简单易懂)

1. 前端能携带请求参数的地方 http请求一半前端请求参数放在三个地方&#xff1a;请求头&#xff0c;请求查询参数&#xff08;Query String&#xff09;&#xff0c;请求体。 请求体需要获取HttpServletRequest对象才能获取。 2. 请求体常见格式 而请求体中可以存放多种格式…

Springboot 订餐管理系统idea开发mysql数据库web结构java编程计算机网页源码maven项目

一、源码特点 springboot 订餐管理系统是一套完善的信息系统&#xff0c;结合springboot框架和bootstrap完成本系统&#xff0c;对理解JSP java编程开发语言有帮助系统采用springboot框架&#xff08;MVC模式开发&#xff09;&#xff0c;系统具有 完整的源代码和数据库&…

大数据与Hadoop入门理论

一、大数据的3种数据类型 1、结构化数据 可定义&#xff0c;有类型、格式、结构的强制约束 如&#xff1a;RDBMS&#xff08;关系型数据库管理系统&#xff09; 2、非结构化数据 没有规律没有数据约束可言&#xff0c;很复杂难以解析 如&#xff1a;文本文件&#xff0c;视…

02 认识Verilog HDL

02 认识Verilog HDL ‍ 对于Verilog的语言的学习&#xff0c;我认为没必要一开始就从头到尾认真的学习这个语言&#xff0c;把这个语言所有细节都搞清楚也不现实&#xff0c;我们能够看懂当前FPGA的代码的程度就可以了&#xff0c;随着学习FPGA深度的增加&#xff0c;再不断的…

Axure RP 9 for Mac(原型设计软件)中文正式版

Axure RP 9 是一款流行的原型设计和线框图软件&#xff0c;允许设计人员和开发人员为网站和移动应用程序创建交互式动态原型。它提供了一整套用于创建交互式设计的工具和功能&#xff0c;包括拖放小部件、条件逻辑、动态内容和动画。 软件下载&#xff1a;Axure RP 9 for Mac中…

2023版 STM32实战7 通用同步/异步收发器(串口)F103/F407

串口简介和习惯 -1-通用同步异步收发器 (USART) 能够灵活地与外部设备进行全双工数据交换&#xff0c;满足外部设备对工业标准 NRZ 异步串行数据格式的要求。 -2-硬件流控制一般是关闭的 -3-波特率指单位时间传输bit个数 -4-数据位一般是8位 -5-一般无校验位 编写代码思路 -1-参…

Java架构师高并发架构设计

目录 1 导学2 什么是高并发问题3 高并发处理之道4 akf扩展立方体5 细化理念应对高并发5 总结1 导学 本章的主要内容是大型系统架构设计的难点之一,高并发架构设计相关的知识落到实际项目上,就是订单系统的高并发架构设计。我们首先会去学习到底何为高并发问题,先把问题搞清楚…

神经网络中卷积和池化的区别

1、什么叫卷积&#xff1f; 卷积层是用一个固定大小的矩形区去席卷原始数据&#xff0c;将原始数据分成一个个和卷积核大小相同的小块&#xff0c;然后将这些小块和卷积核相乘输出一个卷积值&#xff08;注意这里是一个单独的值&#xff0c;不再是矩阵了&#xff09;。 卷积的…

【RabbitMQ 实战】10 消息持久化和存储原理

一、持久化 1.1 持久化对象 rabbitmq的持久化分为三个部分&#xff1a; 交换器的持久化。队列的持久化。消息的持久化。 1.1.1 交换器持久化 交换器的持久化是通过在声明交换器时&#xff0c; 指定Durability参数为durable实现的。若交换器不设置持久化&#xff0c;在rabb…

C++11 Thread线程库的使用

C11 Thread线程库的使用 传统的C&#xff08;C11标准之前&#xff09;中并没有引入线程这个概念&#xff0c;在C11出来之前&#xff0c;如果我们想要在C中实现多线程&#xff0c;需要借助操作系统平台提供的API&#xff0c;比如Linux的&#xff0c;或者windows下的 。 本文详细…