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

【QED】等式构造

文章目录

  • 题目
    • 题目描述
    • 输入输出格式
    • 数据范围
    • 测试样例
  • 思路
  • 代码
  • 复杂度分析
    • 时间复杂度
    • 空间复杂度

题目

题目链接🔗

题目描述

有关 「上述等式为何正确」 的问题解决了,然而 「如何构造出上述那种让人啼笑皆非的正确等式」 成为了一个新的问题。

我们认为这个问题太难了,因此我们把解决这个问题的任务交给了你,相信你可以完成这个任务:给出一个整数 n n n,求出一组整数 x x x y y y z z z,满足 x − y ÷ z = n ! x-y÷z=n! xy÷z=n! ( x − y ) ÷ z = n (x-y)÷z=n (xy)÷z=n

注意, z z z 应为正数。如果有多种可能的答案,输出任意⼀种即可。

输入输出格式

【输入格式】

输入共一行一个整数 n n n

【输出格式】

输出共一行三个整数 x x x y y y z z z,代表满足 x − y ÷ z = n ! x-y÷z=n! xy÷z=n! ( x − y ) ÷ z = n (x-y)÷z=n (xy)÷z=n 的一组整数( z z z为正整数)。三者两两之间以一个空格隔开。

数据范围

0 < n ≤ 11 0 < n \le 11 0<n11 − 1 0 9 ≤ x -10^9 \le x 109x y ≤ 1 0 9 y \le 10^9 y109 1 ≤ z ≤ 1 0 9 1 \le z \le 10^9 1z109

测试样例

input1:

5

output1:

230 220 2

input2:

1

output2:

2 1 1

思路

题目要求满足:
x − y ÷ z = n ! x-y÷z=n! xy÷z=n! ( x − y ) ÷ z = n (x-y)÷z=n (xy)÷z=n y = k ⋅ z y=k·z y=kz k k k 为整数,上面两个式子联立后消去 ,可得: n ! + h = k ⋅ z + n ⋅ 2 n!+h=k·z+n·2 n!+h=kz+n2 z = n ! + k n + k z=\frac{n!+k}{n+k} z=n+kn!+k分子变形加上一个 n n n 再减去一个 n n n 得: z = n + k + n ! − n n + k = 1 + n ! − n n + k z=\frac{n+k+n!-n}{n+k}=1+\frac{n!-n}{n+k} z=n+kn+k+n!n=1+n+kn!n由于 k为整数,此外没有太多其他约束,而考虑到 z ≥ 1 z\geq1 z1 旦对于此式我们只需要求出一组特解即可满足题意,我们可以注意到当 n ! − n n + k = 1 \frac{n!-n}{n+k}=1 n+kn!n=1 时等式成立。这一步是构造的关键。当然我们也可以寻求其他特解,如考虑到 n ! − n n + k \frac{n!-n}{n+k} n+kn!n的分子可以被 n n n整除,我们直接令分母中的 k = 0 k=0 k=0,此时 z = ( n − 1 ) ! z=(n-1)! z=(n1)!也为整数使用 n ! − n n + k = 1 \frac{n!-n}{n+k}=1 n+kn!n=1的特解,可得: k = n ! − 2 n k=n!-2n k=n!2n k k k代入上述方程得: x = 2 n ! − 2 n x=2n!-2n x=2n!2n y = 2 n ! − 4 n y=2n!-4n y=2n!4n z = 2 z=2 z=2
(思路来源于《2024年广东工业大学揭阳校区ACM新生程序设计竞赛题解》)

代码

#include <iostream>
using namespace std;// 计算阶乘的函数
long long fact(long long x) {long long res = 1;for (long long i = 1; i <= x; i++)res *= i;return res;
}int main() {long long n;cin >> n;// 计算 x 和 y 的值long long x = 2 * (fact(n) - n);long long y = 2 * (fact(n) - 2 * n);// 输出结果cout << x << ' ' << y << ' ' << 2;return 0;
}

复杂度分析

时间复杂度

计算阶乘的时间复杂度为 O ( n ) O(n) O(n)

空间复杂度

使用了常数个额外变量,空间复杂度为 O ( 1 ) O(1) O(1)

相关文章:

【QED】等式构造

文章目录 题目题目描述输入输出格式数据范围测试样例 思路代码复杂度分析时间复杂度空间复杂度 题目 题目链接&#x1f517; 题目描述 有关 「上述等式为何正确」 的问题解决了&#xff0c;然而 「如何构造出上述那种让人啼笑皆非的正确等式」 成为了一个新的问题。 我们认…...

Kafka数据迁移全解析:同集群和跨集群

文章目录 一、同集群迁移二、跨集群迁移 Kafka两种迁移场景&#xff0c;分别是同集群数据迁移、跨集群数据迁移。 一、同集群迁移 应用场景&#xff1a; broker 迁移 主要使用的场景是broker 上线,下线,或者扩容等.基于同一套zookeeper的操作。 实践&#xff1a; 将需要新添加…...

Debian安装配置RocketMQ

安装配置 本次安装在/tools/rocket目录下 下载 wget https://dist.apache.org/repos/dist/release/rocketmq/5.3.1/rocketmq-all-5.3.1-bin-release.zip 解压缩 unzip rocketmq-all-5.3.1-bin-release.zip 如果出现以下报错 -bash: unzip: command not found可安装unzip工具后执…...

vue之axios基本使用

文章目录 1. axios 网络请求库2. axiosvue 1. axios 网络请求库 <body> <input type"button" value"get请求" class"get"> <input type"button" value"post请求" class"post"> <!-- 官网提供…...

三只脚的电感是什么东西?

最近在做加湿器&#xff0c;把水雾化的陶瓷片需要有专门的驱动电路。 我参考了某宝卖家的驱动板以及网上的开源项目&#xff0c;发现了驱动电路的核心就是一个三脚电感。 在此之前我都没注意过这玩意&#xff0c;三脚电感不也还是电感嘛&#xff1f; 今天我们就来看看三脚电…...

【数据库学习笔记】SQL触发器(例题+代码)

数据库SQL 1、触发器概念 &#xff08;1&#xff09;触发器&#xff08;trigger&#xff09;是用户定义在关系表上的一类由事件驱动的存储过程&#xff0c;由服务器自动激活。 &#xff08;2&#xff09;触发器可进行更为复杂的检查和操作&#xff0c;具有更精细和更强大的数…...

Unittest02|TestSuite、TestRunner、HTMLTestRunner、处理excel表数据、邮件接收测试结果

目录 八、测试套件TestSuite和测试运行器TestRunner 1、基本概念 2、创建和使用测试套件 3、 自动发现测试用例、创建测试套件、运行测试 4、生成html的测试报告&#xff1a;HTMLTestRunner 1️⃣导入HTMLTestRunner模块 2️⃣运行测试用例并生成html文件 九、unittest…...

BAPI_BATCH_CHANGE在更新后不自动更新批次特征

1、问题介绍 在CL03中看到分类特性配置了制造日期字段&#xff0c;并绑定了生产日期字段MCH1~HSDAT MSC2N修改批次的生产日期字段时&#xff0c;自动修改了对应的批次特性 但是通过BAPI&#xff1a;BAPI_BATCH_CHANGE修改生产日期时&#xff0c;并没有更新到批次特性中 2、BAPI…...

顶会评测集解读-AlignBench: 大语言模型中文对齐基准

评测集社区 CompssHub 作为司南 OpenCompass大模型评测体系的重要组成部分&#xff0c;致力于简化并加快研究人员和行业人士搜索和使用评测集的过程。评测集社区 CompssHub 目前已收录了学科、推理、知识、代码等12个方向的评测集&#xff0c;欢迎大家探索。 为了将评测集社区…...

MySQL外键类型与应用场景总结:优缺点一目了然

前言&#xff1a; MySQL的外键简介&#xff1a;在 MySQL 中&#xff0c;外键 (Foreign Key) 用于建立和强制表之间的关联&#xff0c;确保数据的一致性和完整性。外键的作用主要是限制和维护引用完整性 (Referential Integrity)。 主要体现在引用操作发生变化时的处理方式&…...

【含开题报告+文档+PPT+源码】基于SpringBoot+Vue的网上书店管理系统的设计与实现

开题报告 本研究论文主要介绍了基于Spring Boot框架开发的全面网上书店管理系统的构建与实现。该系统以用户为核心&#xff0c;提供了丰富的个性化服务功能。首先&#xff0c;系统支持用户进行便捷的登录注册操作&#xff0c;并具备安全可靠的密码修改机制&#xff0c;同时允许…...

力扣面试题 - 40 迷路的机器人 C语言解法

题目&#xff1a; 设想有个机器人坐在一个网格的左上角&#xff0c;网格 r 行 c 列。机器人只能向下或向右移动&#xff0c;但不能走到一些被禁止的网格&#xff08;有障碍物&#xff09;。设计一种算法&#xff0c;寻找机器人从左上角移动到右下角的路径。 网格中的障碍物和空…...

ElementPlus 自定义封装 el-date-picker 的快捷功能

文章目录 需求分析 需求 分析 我们看到官网上给出的案例如下&#xff0c;但是不太满足我们用户想要的快捷功能&#xff0c;因为不太多&#xff0c;因此需要我们自己封装一些&#xff0c;方法如下 外部自定义该组件的快捷内容 export const getPickerOptions () > {cons…...

二百八十二、ClickHouse——删除Linux中的ClickHouse

一、目的 由于ClickHosue的库表发生变化&#xff0c;需要删除原有的表结构数据&#xff0c;才能直接把脚本里文件重新安装 二、删除步骤 1、关闭ClickHouse服务 systemctl stop clickhouse-server 2、卸载ClickHouse软件包 sudo yum remove clickhouse-server clickhouse…...

c++ 命名空间使用规则

之前一直没搞懂为什么c 用了using namespace std;就能直接调用内部的类&#xff0c;直接调用内部函数 今天试着实现了一下&#xff1a; #include <iostream>// 命名空间 namespace mp{ class point{public: // 构造函数point(int x 0, int y 0) : x(x), y(y) {}//…...

从 ELK Stack 到简单 — Elastic Cloud Serverless 上的 Elastic 可观察性

作者&#xff1a;来自 Elastic Bahubali Shetti, Chris DiStasio 宣布 Elastic Cloud Serverless 上的 Elastic Observability 正式发布 — 一款完全托管的可观察性解决方案。 随着组织规模的扩大&#xff0c;一个能够处理分布式云环境的复杂性并提供实时洞察的可观察性解决方…...

Pandas系列|第二期:Pandas中的数据结构

1.Pandas中的数据结构&#xff1a;Series和DataFrame Pandas 的主要数据结构是 Series &#xff08;一维数据&#xff09;与 DataFrame&#xff08;二维数据&#xff09;&#xff0c;这两种数据结构足以处理金融、统计、社会科学、工程等领域里的大多数典型用例。 Series 是一…...

Hadoop中MapReduce过程中Shuffle过程实现自定义排序

文章目录 Hadoop中MapReduce过程中Shuffle过程实现自定义排序一、引言二、实现WritableComparable接口1、自定义Key类 三、使用Job.setSortComparatorClass方法2、设置自定义排序器3、自定义排序器类 四、使用示例五、总结 Hadoop中MapReduce过程中Shuffle过程实现自定义排序 一…...

数位dp-acwing

题目&#xff1a;Windy数 1083. Windy数 - AcWing题库 分析 不能有前导0&#xff0c;初始化的时候需要有前导0&#xff0c;因为除了最高位数其他位数可以。 windy &#xff1a; 2 5 1 类似这样的数 第二位与第一位相差3 > 2 分类讨论 &#xff1a; 1. 位数跟 n 同位数 的…...

智慧园区小程序开发制作功能介绍

智慧园区小程序开发制作功能介绍 智慧园区小程序系统作为一款面向园区企业的一站式线上服务平台&#xff0c;可为企业提供数智化的园区办公服务。智慧园区小程序功能介绍 1、园区公告、政策信息查看足不出户掌握最新动态&#xff0c;“园区公告、政策信息”等信息。首页点击对应…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Reasoning over Uncertain Text by Generative Large Language Models

https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...