ZT36 小红和小紫的取素因子游戏
描述
小红和小紫拿到了一个正整数x,她们每次可以选择x的一个因子k(k>1),把x除以k,但要求k必须是素数。小红先手,谁先不能操作谁输。假设两人都足够聪明,最终谁取得胜利?
共进行t次游戏。输入描述:
第一行输入一个正整数t,代表游戏的轮数。
接下来的t行,每行输入一个正整数x,代表小红和小紫拿到的正整数。
1≤t≤10
1≤x≤10^9输出描述:
对于每次游戏:
如果小红获胜,输出一行字符串"kou"
如果小紫获胜,输出一行字符串"yukari"示例1
输入:
2 5 12输出:
kou kou说明:
共有2次游戏。 第一次她们拿到的数是5,小红取5,5/5=1,小紫无法继续取数,小红获胜。 第二次她们拿到的数是12,小红取12的素因子2,12/2=6,小紫取6的素因子2,6/2=3,小红取3的素因子3,3/3=1,然后小紫无法继续取数,小红获胜。
一、问题分析
首先读题,仔细看描述中的内容,发现需求是
1.给t个整数
2.对于每个整数x,有小红和小紫两个人
3.他们每次需要选择x的一个因子k,将x除以k
4.但是这个k必须是素数
5.小红先手,谁先不能操作谁输,假设两个人都足够聪明,问每次胜利者是谁
6.如果是小红输出kou如果是小紫输出yukari
二、解题思路
1.快速幂算法
三、具体步骤
使用的语言是C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>typedef __int128 int128;// 求最大公约数(欧几里得算法)
int gcd(int a, int b) {if (b == 0)return a;return gcd(b, a % b);
}// 快速幂算法
int quick_pow(int x, int p, int mod) {int ans = 1;while (p) {if (p & 1)ans = (int128)ans * x % mod;x = (int128)x * x % mod;p >>= 1;}return ans;
}// 判断素数(Miller-Rabin算法)
int Miller_Rabin(int p) {if (p < 2)return 0;if (p == 2)return 1;if (p == 3)return 1;int d = p - 1, r = 0;while (!(d & 1)) {++r;d >>= 1;}for (int k = 0; k < 10; ++k) {int a = rand() % (p - 2) + 2;int x = quick_pow(a, d, p);if (x == 1 || x == p - 1)continue;for (int i = 0; i < r - 1; ++i) {x = (int128)x * x % p;if (x == p - 1)break;}if (x != p - 1)return 0;}return 1;
}// 取绝对值函数
int ABS(int a) {return (a < 0) ? -a : a;
}// Pollard-Rho算法进行整数分解
int Pollard_Rho(int x) {int s = 0, t = 0;int c = rand() % (x - 1) + 1;int step = 0, goal = 1;int val = 1;for (goal = 1;; goal *= 2, s = t, val = 1) {for (step = 1; step <= goal; ++step) {t = ((int128)t * t + c) % x;val = (int128)val * ABS(t - s) % x;if ((step % 127) == 0) {int d = gcd(val, x);if (d > 1)return d;}}int d = gcd(val, x);if (d > 1)return d;}
}// 分解整数x的质因数,并更新最大质因数等相关操作
void fac(int x, int* max_factor) {if (x <= *max_factor || x < 2)return;if (Miller_Rabin(x)) {*max_factor = (*max_factor > x) ? *max_factor : x;return;}int p = x;while (p >= x)p = Pollard_Rho(x);while ((x % p) == 0)x /= p;fac(x, max_factor);fac(p, max_factor);
}// 从标准输入读取一个整数
int read() {int x = 0, f = 1;char c = getchar();while (c < '0' || c > '9') {if (c == '-')f = -1;c = getchar();}while (c >= '0' && c <= '9') {x = x * 10 + (c - '0');c = getchar();}return f * x;
}int main() {srand((unsigned int)time(NULL));int T = read();while (T--) {int x = read();int z = 0;while (x != 1) {int max_factor = 0;z++;fac(x, &max_factor);x /= max_factor;}if (z % 2 == 1)printf("kou\n");elseprintf("yukari\n");}return 0;
}
相关文章:
ZT36 小红和小紫的取素因子游戏
描述 小红和小紫拿到了一个正整数x,她们每次可以选择x的一个因子k(k>1),把x除以k,但要求k必须是素数。小红先手,谁先不能操作谁输。假设两人都足够聪明,最终谁取得胜利? 共进行t次游戏。 输入描述&…...
C# 使用 Newtonsoft.Json 序列化和反序列化对象实例
Newtonsoft.Json(也被称为 Json.NET)是一个广泛使用的用于在 C# 中进行 JSON 序列化和反序列化的开源库。下面将详细介绍如何使用它来序列化和反序列化对象。 1. 安装 Newtonsoft.Json 如果你使用的是 Visual Studio,可以通过 NuGet 包管理…...
用 AI 工具提升 UX/UI 设计效率:从研究到原型
—————————————————— 用 AI 工具提升 UX/UI 设计效率:从研究到原型 开篇引言: 在 UX/UI 设计领域,效率与创意之间的平衡一直是设计师们追求的目标。随着 AI 工具的崛起,设计师们不仅能更快地完成任务,…...
操作系统知识点12
1.在操作系统的结构设计中,采用层次结构的操作系统其最大优点是把整体问题局部化 2.非特权指令是指操作系统和用户均可以使用的指令 3.向处理器发出的中断信号称为中断请求 4.轮转法RR是单纯基于时间片考虑的 5.当进程处于就绪状态时,表示进程已获得…...
FASIONAD:自适应反馈的类人自动驾驶中快速和慢速思维融合系统
24年11月来自清华、早稻田大学、明尼苏达大学、多伦多大学、厦门大学马来西亚分校、电子科大(成都)、智平方科技和河南润泰数字科技的论文“FASIONAD : FAst and Slow FusION Thinking Systems for Human-Like Autonomous Driving with Adaptive Feedbac…...
Redis7——基础篇(八)
前言:此篇文章系本人学习过程中记录下来的笔记,里面难免会有不少欠缺的地方,诚心期待大家多多给予指教。 基础篇: Redis(一)Redis(二)Redis(三)Redis&#x…...
nvm安装
1.下载安装包 从官网下载https://github.com/nvm-sh/nvm/releases 这里下的是nvm-0.40.1.tar.gz 2.解压 tar -zxvf nvm-0.40.1.tar.gz 3. 修改配置文件 vi ~/.bashrc 在最后一行添加如下内容 export NVM_DIR"/usr/local/nvm-0.40.1"[ -s "$NVM…...
基于vue框架的游戏博客网站设计iw282(程序+源码+数据库+调试部署+开发环境)带论文文档1万字以上,文末可获取,系统界面在最后面。
系统程序文件列表 项目功能:用户,博客信息,资源共享,游戏视频,游戏照片 开题报告内容 基于FlaskVue框架的游戏博客网站设计开题报告 一、项目背景与意义 随着互联网技术的飞速发展和游戏产业的不断壮大,游戏玩家对游戏资讯、攻略、评测等内容的需求日…...
spring MVC执行流程
详细的项目结构 src ├── main │ ├── java │ │ ├── com.example │ │ │ ├── config │ │ │ │ └── SpringMvcInitializer.java // 配置 DispatcherServlet │ │ │ │ └── SpringConfig.java // Sprin…...
递归遍历目录 和 普通文件的复制 [Java EE]
递归遍历目录 首先 先列出当前目录所包含的内容 File[] files currentDir.listFiles();if (files null || files.length 0) {// 若是空目录或非法目录, 则直接返回return;} 然后 遍历列出的文件, 分情况两种讨论 for (File f: files) {// 加个日志, 方便查看程序执行情…...
如何在docker上部署java服务
目录结构 首先 Dockerfile FROM bladex/alpine-java:openjdk17_cn_slimMAINTAINER admin@rsz.comENV TZ=Asia/ShanghaiRUN ln -sf /usr/share/zoneinfo/$TZ /etc/localtime && echo $TZ > /etc/timezoneRUN mkdir -p /xhWORKDIR /xhEXPOSE 8106ADD ./blade-system.…...
Machine Learning 初探
前置知识 pandas 读取文件:read_csv查看信息 describe:查看整体信息,包括每列的平均值、最大最小值、标准差等head:输出头部几行数据columns:输出所有列名loc:查询数据,或是根据索引取对应的数…...
GESP2024年12月认证C++三级( 第三部分编程题(1)数字替换)
参考程序: #include <iostream> #include <vector> #include <algorithm> using namespace std; int a[100010]; // 定义一个数组a,用于存储序列A,数组大小为100010 int main() {int n, k; // 定义变量n和k,…...
IDEA-插件开发踩坑记录-第六坑-UAST依赖问题
背景 简要说明: UAST – Unified Abstract Syntax Tree UAST (Unified Abstract Syntax Tree) is an abstraction layer on the PSI of different programming languages targeting the JVM (Java Virtual Machine). It provides a unified API for working with co…...
单片机总结【GPIO/TIM/IIC/SPI/UART】
一、GPIO 1、概念 通用输入输出口;开发者可以根据自己的需求将其配置为输入或输出模式,以实现与外部设备进行数据交互、控制外部设备等功能。简单来说,GPIO 就像是计算机或微控制器与外部世界沟通的 “桥梁”。 2、工作模式 工作模式性质特…...
信号和槽
connect(信号发送者,发送的信号,信号接收者,信号的处理); 信号函数和槽函数的参数必须是一样的,但信号的参数可以多余槽函数的参数(前面的参数类型必须一致) 是控件和控件间的信号传递,这两个…...
Window下Redis的安装和部署详细图文教程(Redis的安装和可视化工具的使用)
文章目录 Redis下载地址:一、zip压缩包方式下载安装 1、下载Redis压缩包2、解压到文件夹3、启动Redis服务4、打开Redis客户端进行连接5、使用一些基础操作来测试 二、msi安装包方式下载安装 1、下载Redis安装包2、进行安装3、进行配置4、启动服务5、测试能否正常工…...
1.2.3 使用Spring Initializr方式构建Spring Boot项目
本实战概述介绍了如何使用Spring Initializr创建Spring Boot项目,并进行基本配置。首先,通过Spring Initializr生成项目骨架,然后创建控制器HelloController,定义处理GET请求的方法hello,返回HTML字符串。接着…...
数据可视化02-PCA降维
一、PCA PCA做什么?找坐标系。 目标?二维降到一维,信息保留最多。 怎么样最好?数据分布最分散的方向(方差最大),作为主成分(坐标轴)。 二、怎么找主成分? …...
大连指令数据集的创建--数据收集与预处理_02
1.去哪儿爬虫 编程语言:Python爬虫框架:Selenium(用于浏览器自动化)解析库:BeautifulSoup(用于解析HTML) 2.爬虫策略 目标网站:去哪儿(https://travel.qunar.com/trav…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
基于ASP.NET+ SQL Server实现(Web)医院信息管理系统
医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上,开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识,在 vs 2017 平台上,进行 ASP.NET 应用程序和简易网站的开发;初步熟悉开发一…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
