当前位置: 首页 > 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…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案

一、延迟敏感行业面临的DDoS攻击新挑战 2025年&#xff0c;金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征&#xff1a; AI驱动的自适应攻击&#xff1a;攻击流量模拟真实用户行为&#xff0c;差异率低至0.5%&#xff0c;传统规则引…...

STM32标准库-ADC数模转换器

文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”&#xff1a;输入模块&#xff08;GPIO、温度、V_REFINT&#xff09;1.4.2 信号 “调度站”&#xff1a;多路开关1.4.3 信号 “加工厂”&#xff1a;ADC 转换器&#xff08;规则组 注入…...

react菜单,动态绑定点击事件,菜单分离出去单独的js文件,Ant框架

1、菜单文件treeTop.js // 顶部菜单 import { AppstoreOutlined, SettingOutlined } from ant-design/icons; // 定义菜单项数据 const treeTop [{label: Docker管理,key: 1,icon: <AppstoreOutlined />,url:"/docker/index"},{label: 权限管理,key: 2,icon:…...