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

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&#xff0c;她们每次可以选择x的一个因子k(k>1)&#xff0c;把x除以k&#xff0c;但要求k必须是素数。小红先手&#xff0c;谁先不能操作谁输。假设两人都足够聪明&#xff0c;最终谁取得胜利&#xff1f; 共进行t次游戏。 输入描述&…...

C# 使用 Newtonsoft.Json 序列化和反序列化对象实例

Newtonsoft.Json&#xff08;也被称为 Json.NET&#xff09;是一个广泛使用的用于在 C# 中进行 JSON 序列化和反序列化的开源库。下面将详细介绍如何使用它来序列化和反序列化对象。 1. 安装 Newtonsoft.Json 如果你使用的是 Visual Studio&#xff0c;可以通过 NuGet 包管理…...

用 AI 工具提升 UX/UI 设计效率:从研究到原型

—————————————————— 用 AI 工具提升 UX/UI 设计效率&#xff1a;从研究到原型 开篇引言&#xff1a; 在 UX/UI 设计领域&#xff0c;效率与创意之间的平衡一直是设计师们追求的目标。随着 AI 工具的崛起&#xff0c;设计师们不仅能更快地完成任务&#xff0c…...

操作系统知识点12

1.在操作系统的结构设计中&#xff0c;采用层次结构的操作系统其最大优点是把整体问题局部化 2.非特权指令是指操作系统和用户均可以使用的指令 3.向处理器发出的中断信号称为中断请求 4.轮转法RR是单纯基于时间片考虑的 5.当进程处于就绪状态时&#xff0c;表示进程已获得…...

FASIONAD:自适应反馈的类人自动驾驶中快速和慢速思维融合系统

24年11月来自清华、早稻田大学、明尼苏达大学、多伦多大学、厦门大学马来西亚分校、电子科大&#xff08;成都&#xff09;、智平方科技和河南润泰数字科技的论文“FASIONAD : FAst and Slow FusION Thinking Systems for Human-Like Autonomous Driving with Adaptive Feedbac…...

Redis7——基础篇(八)

前言&#xff1a;此篇文章系本人学习过程中记录下来的笔记&#xff0c;里面难免会有不少欠缺的地方&#xff0c;诚心期待大家多多给予指教。 基础篇&#xff1a; Redis&#xff08;一&#xff09;Redis&#xff08;二&#xff09;Redis&#xff08;三&#xff09;Redis&#x…...

nvm安装

1.下载安装包 从官网下载https://github.com/nvm-sh/nvm/releases 这里下的是nvm-0.40.1.tar.gz 2&#xff0e;解压 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万字以上,文末可获取,系统界面在最后面。

系统程序文件列表 项目功能&#xff1a;用户,博客信息,资源共享,游戏视频,游戏照片 开题报告内容 基于FlaskVue框架的游戏博客网站设计开题报告 一、项目背景与意义 随着互联网技术的飞速发展和游戏产业的不断壮大&#xff0c;游戏玩家对游戏资讯、攻略、评测等内容的需求日…...

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 读取文件&#xff1a;read_csv查看信息 describe&#xff1a;查看整体信息&#xff0c;包括每列的平均值、最大最小值、标准差等head&#xff1a;输出头部几行数据columns&#xff1a;输出所有列名loc&#xff1a;查询数据&#xff0c;或是根据索引取对应的数…...

GESP2024年12月认证C++三级( 第三部分编程题(1)数字替换)

参考程序&#xff1a; #include <iostream> #include <vector> #include <algorithm> using namespace std; int a[100010]; // 定义一个数组a&#xff0c;用于存储序列A&#xff0c;数组大小为100010 int main() {int n, k; // 定义变量n和k&#xff0c;…...

IDEA-插件开发踩坑记录-第六坑-UAST依赖问题

背景 简要说明&#xff1a; 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、概念 通用输入输出口&#xff1b;开发者可以根据自己的需求将其配置为输入或输出模式&#xff0c;以实现与外部设备进行数据交互、控制外部设备等功能。简单来说&#xff0c;GPIO 就像是计算机或微控制器与外部世界沟通的 “桥梁”。 2、工作模式 工作模式性质特…...

信号和槽

connect(信号发送者&#xff0c;发送的信号&#xff0c;信号接收者&#xff0c;信号的处理); 信号函数和槽函数的参数必须是一样的&#xff0c;但信号的参数可以多余槽函数的参数&#xff08;前面的参数类型必须一致&#xff09; 是控件和控件间的信号传递&#xff0c;这两个…...

Window下Redis的安装和部署详细图文教程(Redis的安装和可视化工具的使用)

文章目录 Redis下载地址&#xff1a;一、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项目&#xff0c;并进行基本配置。首先&#xff0c;通过Spring Initializr生成项目骨架&#xff0c;然后创建控制器HelloController&#xff0c;定义处理GET请求的方法hello&#xff0c;返回HTML字符串。接着&#xf…...

数据可视化02-PCA降维

一、PCA PCA做什么&#xff1f;找坐标系。 目标&#xff1f;二维降到一维&#xff0c;信息保留最多。 怎么样最好&#xff1f;数据分布最分散的方向&#xff08;方差最大&#xff09;&#xff0c;作为主成分&#xff08;坐标轴&#xff09;。 二、怎么找主成分&#xff1f; …...

大连指令数据集的创建--数据收集与预处理_02

1.去哪儿爬虫 编程语言&#xff1a;Python爬虫框架&#xff1a;Selenium&#xff08;用于浏览器自动化&#xff09;解析库&#xff1a;BeautifulSoup&#xff08;用于解析HTML&#xff09; 2.爬虫策略 目标网站&#xff1a;去哪儿&#xff08;https://travel.qunar.com/trav…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

学习一下用鸿蒙​​DevEco Studio HarmonyOS5实现百度地图

在鸿蒙&#xff08;HarmonyOS5&#xff09;中集成百度地图&#xff0c;可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API&#xff0c;可以构建跨设备的定位、导航和地图展示功能。 ​​1. 鸿蒙环境准备​​ ​​开发工具​​&#xff1a;下载安装 ​​De…...