Problem 2125 简单的等式(FZU),,数学题。。。
2024-08-30 13:45:09
Problem 2125 简单的等式
Time Limit: 1000 mSec
Memory Limit : 32768 KB
Problem Description
现在有一个等式如下:x^2+s(x,m)x-n=0。其中s(x,m)表示把x写成m进制时,每个位数相加的和。现在,在给定n,m的情况下,求出满足等式的最小的正整数x。如果不存在,请输出-1。
Input
有T组测试数据。以下有T(T<=100)行,每行代表一组测试数据。每个测试数据有n(1<=n<=10^18),m(2<=m<=16)。
Output
输出T行,有1个数字,满足等式的最小的正整数x。如果不存在,请输出-1。
Sample Input
4
4 10
110 10
15 2
432 13
Sample Output
-1
10
3
18
我只想说这道题的后台测试数据水啊,,,题目所给的数据范围挺大的,,有超时的风险,,但思路很好想,。。。要使x*(x+sum)==n,sum=s(x,m),,从x角度出发,,x<=sqrt(n)--这个应该不用解释吧,,然后用for循环遍历看是否能找到,但限制条件是什么呢?,,我们知道,,这个数据范围(10^18)内的数转化成进制数位数和是不会超过100的,即sum不大于100;
于是便有了限制条件,, if(n/i-i>=100) break;
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<ctype.h>
using namespace std;
int main()
{
int t,m;
long long n;
long long i;
scanf("%d",&t);
while(t--)
{
scanf("%I64d%d",&n,&m);
long long x=sqrt(n);
int f=0;
for( i=x;i>0 ; i--)
{
long long x1=i;
long long sum=0;
while(x1)
{
sum+=x1%m;
x1/=m;
}
if(i*(i+sum)==n)
{
f=1;
break;//题目已经说了输出最小的x,,但这样也能过,,无语;
}
if(n/i-i>=100)
break;
}
if(f)
printf("%I64d\n",i);
else
printf("-1\n");
}
return 0;
}
也可以从sum的角度出发,,因为sum的范围并不大,,已知m就可以还原x再判断即可;
但前提是要知道进制转换后位和不大于100;;;555555~~
最新文章
- Java面试题整理
- Clipboard.js – 现代方式实现复制文本到剪贴板
- MYSQL 基于GTID的复制
- Qt——正则表达式
- archlinux下查看机器的ip地址
- 阿里云slb http https配置
- Android - 封装Fragment不依赖于Activity
- JSP 内置对象的四种属性范围
- QPainter就是手里的作图工具,只需要三洋东西:笔(颜色,宽度,样式),字体(写字),刷子(大面积作画),这里有三个典型例子
- MES工具机器列表功能操作
- Mysql创建索引
- Collection集合详解
- [Alpha阶段]无人转会申请
- Java 错误提示org.apache.poi.POIXMLException: java.lang.reflect.InvocationTargetException
- 受限filterbanks
- mysql原生sql盘点
- 【Java基础】char
- Kubernetes基础概念及架构概述
- [转]用JAVA在读取EXCEL文件时如何判断列隐藏
- requestmapping等相关知识
热门文章
- 转-sql之left join、right join、inner join的区别
- phpcms v9模板制作教程
- mysql单向自动同步
- STM32&;AT指令NBIOT模组
- ubuntu下安装apcu扩展
- 【HEVC帧间预测论文】P1.9 Coding Tree Depth Estimation for Complexity Reduction of HEVC
- javaee 第六周作业
- Android中单选框RadioButton的基本用法
- 通过JS加载XML文件,跨浏览器兼容
- 为什么我的 app:actionViewClass=";android.widget.SearchView";和app:showAsAction=";ifRoom|collapseActionView";才有