Atcoder ABC397-D 题解

https://atcoder.jp/contests/abc397/tasks/abc397_dhttps://atcoder.jp/contests/abc397/tasks/abc397_d

题目描述:

确定是否存在一对正整数(x,y),使得x^3-y^3=N


思路:

首先对方程进行转化

k=x-y

\because N=x^3-y^3=x^3-(x-k)^3=x^3-(x^3-3x^2k+3xk^2-k^3)

\therefore N=x^3-y^3=3x^2k-3xk^2+k^3

3x^2k-3xk^2+k^3-N=0

接下来确定k的范围

根据立方差公式

N=x^3-y^3=(x-y)(x^2+xy+y^2)=k(x^2+xy+y^2)

\because x>0,y>0     \therefore xy>0

\therefore k(x^2+xy+y^2)\geq k(x^2-2xy+y^2)=k\cdot k^2=k^3

\therefore N\geq k^3    \therefore k\leq \sqrt[3]{N}

\because N\leq 10^{18}

\therefore k\leq \sqrt[3]{n}\leq 10^{6}

因此,我们可以从1\sqrt[3]{N}来逐个枚举k

此时 方程的k就变成了常数

a=3k , b=-3k^2 , c=k^3-N

原方程变为ax^2+bx+c=0

这时,只需要解一下这个二次方程就可以了

x=\frac{-b\pm \sqrt {b^2-4ac}}{2a}

提醒:

\because b=-3k^2\geq -10^{12}

\therefore b^2\leq10 ^{24}   会爆long long

所以要开__int128


代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
signed main(){cin>>n;for(int i=1;i*i*i<=n;i++){int a=3*i,b=-3*i*i,c=i*i*i-n;__int128 u=b,v=a;u=u*u-4*v*c;__int128 k=sqrtl(u);if(k*k==u){int xa=(-b+k),xb=(-b-k);if(xa>0&&xa%(2*a)==0&&xa/2/a-i>0){xa/=(2*a);cout<<xa<<" "<<xa-i;return 0;}if(xb>0&&xb%(2*a)==0&&(xb/2/a)-i>0){xb/=(2*a);cout<<xb<<" "<<xb-i;return 0;}}}cout<<"-1";return 0;
}

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

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

相关文章

医疗送药机器人“空间拓扑优化+动态算法决策+多级容错控制”三重链式编程技术解析与应用

一、引言 1.1 研究背景与意义 在医疗体系中,高效精准的药品配送是保障医疗服务质量和患者安全的关键环节。随着医疗技术的不断进步和医疗需求的日益增长,传统的人工送药方式逐渐暴露出诸多弊端,如配送效率低下、易受人为因素干扰导致错误率上升、人力成本高昂等。特别是在…

Redis实现高并发排行榜的功能

生活中排行榜是常见的功能&#xff0c;如游戏的排行榜&#xff0c;销售额的排行榜等等&#xff0c;排行榜不仅可以让用户有更多的激情参与到活动中来&#xff0c;而且可以更好的留存住用户&#xff0c;如下所示的拉新排行榜&#xff1a; 排行榜是一个常见的业务需求&#xff0…

数字孪生像魔镜,映照出无限可能的未来

在当今科技飞速发展的时代&#xff0c;数字孪生作为一项极具潜力的前沿技术&#xff0c;正逐渐崭露头角&#xff0c;成为众多领域关注的焦点。它犹如一面神奇的魔镜&#xff0c;以数字化的方式精准映照出现实世界中的各种实体与系统&#xff0c;为我们开启了一扇通往无限可能未…

每日一题---

深拷贝和浅拷贝的区别是什么&#xff1f; null 浅拷贝是指只复制对象本身和其内部的值类型字段&#xff0c;但不会复制对象内部的引用类型字段。换句话说&#xff0c;浅拷贝只是创建一个新的对象&#xff0c;然后将原对象的字段值复制到新对象中&#xff0c;但如果原对象内部有…

Chrome 扩展开发 API实战:Sessions (六)

1. 引言 chrome.sessions 是 Chrome 扩展开发者工具的一部分&#xff0c;提供了对最近关闭的标签页和窗口的访问&#xff0c;以及对会话恢复功能的支持。现代浏览器的一个显著特点是为用户提供更多的便利性&#xff0c;比如快速恢复意外关闭的页面。通过 chrome.sessions API&…

Spring Boot对接twilio发送邮件信息

要在Spring Boot应用程序中对接Twilio发送邮件信息&#xff0c;您可以使用Twilio的SendGrid API。以下是一个简单的步骤指南&#xff0c;帮助您完成这一过程&#xff1a; 1. 创建Twilio账户并获取API密钥 注册一个Twilio账户&#xff08;如果您还没有的话&#xff09;。在Twi…

学习15天:pytest

1、.pytest强大的插件 pytest-html(生成html格式的自动化测试报告) pytest-xdist测试用例分布式执行。多CPU分发。 pytest-ordering 用于改变测试用例的执行顺序 pytest-rerunfailures用例失败后重跑 allure-pytest 用于生成美观的测试报告。 2、规则&#xff1a; 模块…

Springboot+mybatis实现增删改查操作

继续写一下删除操作&#xff0c;删除有些不一样&#xff0c;首先在controller里面&#xff0c;我们需要改一下路由&#xff0c;我们后面要写/{id}传入路径参数&#xff0c;用PathVariable注解绑定id&#xff0c;剩下的都一样&#xff0c;传入id&#xff0c;然后写service和mapp…

Visual Studio里的调试(debugging)功能介绍

参考 1- Introduction to Debugging | Basic Visual Studio Debugging&#xff08;这是一位印度博主视频&#xff0c;我下面做到笔记也主要参考她的视频&#xff0c;但不得不说口音太重了&#xff0c;一股咖喱味&#xff09; 目录 个人对调试浅显的认识和对调试的介绍逐行调…

Java多线程与高并发专题——原子类和 volatile、synchronized 有什么异同?

原子类和 volatile异同 首先&#xff0c;通过我们对原子类和的了解&#xff0c;原子类和volatile 都能保证多线程环境下的数据可见性。在多线程程序中&#xff0c;每个线程都有自己的工作内存&#xff0c;当多个线程访问共享变量时&#xff0c;可能会出现一个线程修改了共享变…

c语言笔记 作用域

目录 作用域的基本概念 1.函数声明的作用域 2.局部变量的作用域 3.全局作用域 4.static修饰后的作用域 作用域的基本概念 在c语言中&#xff0c;我们的标志符是具有一定的可见范围的&#xff0c;我们称这个可见范围为作用域 在软件开发中&#xff0c;我们要确定好标识符的作…

MySQL数据库知识总结

MySQL数据库知识总结 一、基本概念及其介绍二、数据库中的数据类型&#xff08;一&#xff09;数值类型&#xff08;二&#xff09;字符串类型&#xff08;三&#xff09;日期类型 三、数据库基础语法&#xff08;一&#xff09;数据库的常用操作&#xff08;二&#xff09;数据…

SpaceSync智能排班:重构未来办公空间的神经中枢

文心智能体平台可免费使用DeepSeek 满血版啦&#xff0c;使用DeepSeek模型创建并提交智能体&#xff0c;即有机会瓜分万元奖金&#xff01;有这等好事还不快冲&#xff01; 文心智能体官网&#xff1a;文心智能体平台AgentBuilder | 想象即现实 本片文章为作者参加文心智能体平…

Blender-MCP服务源码3-插件开发

Blender-MCP服务源码3-插件开发 Blender-MCP服务源码解读-如何进行Blender插件开发 1-核心知识点 1&#xff09;使用Blender开发框架学习如何进行Blender调试2&#xff09;学习目标1-移除所有的Blender业务-了解如何MCP到底做了什么&#xff1f;3&#xff09;学习目标2-模拟MC…

每日一题---dd爱框框(Java中输入数据过多)

dd爱框框 实例&#xff1a; 输入&#xff1a; 10 20 1 1 6 10 9 3 3 5 3 7 输出&#xff1a; 3 5 这道题要解决Java中输入的数过多时&#xff0c;时间不足的的问题。 应用这个输入模板即可解决&#xff1a; Java中输入大量数据 import java.util.*; import java.io.*;pu…

Qlik Sense New Install with Restore

Background In case you meet the upgrade issue like us , you can follow the below step to recover the existing data to new installed Qlik Sense . Powered by Moshow郑锴-CSDN博客 please follow below steps: pgsql dump backupbackup table into sql by DBeaverst…

大数据-spark3.5安装部署之standalone模式

真实工作中还是要将应用提交到集群中去执行&#xff0c;Standalone模式就是使用Spark自身节点运行的集群模式&#xff0c;体现了经典的master-slave模式。集群共三台机器&#xff0c;具体如下 u22server4spark&#xff1a; master worker u22server4spark2&#xff1a; worke…

Uniapp 开发 App 端上架用户隐私协议实现指南

文章目录 引言一、为什么需要用户隐私协议&#xff1f;二、Uniapp 中实现用户隐私协议的步骤2.1 编写隐私协议内容2.2 在 Uniapp 中集成隐私协议2.3 DCloud数据采集说明2.4 配置方式3.1 Apple App Store3.2 Google Play Store 四、常见问题与解决方案4.1 隐私协议内容不完整4.2…

【C++】 —— 笔试刷题day_5

刷题day_5 一、游游的you 题目链接&#xff1a;游游的you 题目解析 题目要求&#xff1a; 输入a&#xff0c;b&#xff0c;c表示y、o、u三个字母的个数&#xff1b; 将这些字母连成字符串&#xff0c;并且这里you三个字母相邻获得2分&#xff0c;两个o字母相邻获得1分。 让我…

78. Harmonyos NEXT 懒加载数据源实现解析:BasicDataSource与CommonLazyDataSourceModel详解

温馨提示&#xff1a;本篇博客的详细代码已发布到 git : https://gitcode.com/nutpi/HarmonyosNext 可以下载运行哦&#xff01; Harmonyos NEXT 懒加载数据源实现解析&#xff1a;BasicDataSource与CommonLazyDataSourceModel详解 文章目录 Harmonyos NEXT 懒加载数据源实现解…