李韬_varyshare

## 题目描述

X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。

16,24,36,54

3

1250 200 32

25/4

4

3125 32 32 200

5/2

3

549755813888 524288 2

4/1

## 思路：

1. 将所有数互相整除，获得整除后的结果集合。

3125除32=3125/32
3125除200=125/8
32除32=1/1
32除200=25/4

q可以看做q^1，所以在整除后数列中应该所有数都是公比q的整数次方。

``````int x=25/4;

while(x>q){

x=x/q;

}

if(x==1)

print("x是q的整数次方");``````

## 具体代码

``````
import java.math.BigInteger;
import java.util.Iterator;
import java.util.Set;
//用于保存一个分数避免出现除不断情况
class fenshu {
public BigInteger top;
public BigInteger below;

fenshu() {
}

fenshu(BigInteger top, BigInteger below) {
this.top = top;
this.below = below;
}
}

public class XMax {
//求最大公约数
public static BigInteger f(BigInteger a, BigInteger b) {
if (a.signum() == 0)
return b;
return f(b.mod(a), a);
}
//假设的公比的分子
public static BigInteger mintop = new BigInteger("1000000000000");
//假设公比的分母
public static BigInteger minbelow = new BigInteger("1000000000000");
//最小的分子
public static BigInteger tempmintop;
//保存奖金数值
public static BigInteger[] digit;
public static int n;
public static BigInteger temp;
//保存整除后的数列
public static Set<fenshu> set = new LinkedHashSet<>();

public static void fmin(int step) {
if (step >= n)
return;
for (int i = step + 1; i < n; i++) {
temp = f(digit[step], digit[i]);
boolean flag = true;
fenshu t = new fenshu();
if (digit[step].compareTo(digit[i]) > 0) {
t.top = tempmintop = digit[step].divide(temp);
t.below = digit[i].divide(temp);
} else {
t.top = tempmintop = digit[i].divide(temp);
t.below = digit[step].divide(temp);
flag = false;
}
if (!tempmintop.equals(BigInteger.ONE)
&& tempmintop.compareTo(mintop) < 0) {
mintop = tempmintop;
if (flag)
minbelow = digit[i].divide(temp);
else
minbelow = digit[step].divide(temp);
}
}
fmin(step + 1);
}

public static void main(String[] args) {
digit = new BigInteger[] { new BigInteger("549755813888"),
new BigInteger("524288"), new BigInteger("2") };
n = digit.length;
fmin(0);//计算出不同两位数相除得到的商，这些商可能存在公比
Iterator iter = set.iterator();
fenshu t = new fenshu();
while (iter.hasNext()) {
t = (fenshu) iter.next();
while (t.top.compareTo(mintop) > 0) {
t.top = t.top.divide(mintop);
t.below = t.below.divide(minbelow);
}
//如果等于1证明能整除，如果不等于1证明mintop/minbelow还不够小，目前的t.top/t.below更小更适合。
if (!t.top.equals(BigInteger.ONE)) {
mintop = t.top;
minbelow = t.below;
}
}
System.out.println(mintop + "/" + minbelow);
}
}
``````

### 李韬_varyshare

2016/11/29
581
7

2017/03/21
288
3
【蓝桥杯】2019第十届蓝桥杯B组C++年号字串

Debug客栈
03/27
0
0

solopiggy
2013/01/15
285
2
2019年第十届蓝桥杯B组C++省赛手记

Debug客栈
03/25
0
0

好程序员大数据教程Scala系列之样例类_Option_偏函数，在Scala中Option类型样例类用来表示可能存在或也可能不存在的值(Option的子类有Some和None)。Some包装了某个值，None表示没有值。 ...

29分钟前
4
0
zk中ServerCnxnFactory连接管理工厂

30分钟前
6
0
【代码审计01】几种常见的漏洞种类以及代码审计工具

31分钟前
5
0

33分钟前
4
0
【进阶之定义函数】一个查询树结构数据的集合

1、基本定义 delimiter 自定义符号　　-- 如果函数体只有一条语句, begin和end可以省略, 同时delimiter也可以省略create function 函数名(形参列表) returns 返回类型　　-- 注意是retru...

39分钟前
3
0