分享到plurk 分享到twitter 分享到facebook

POJ 2769 - Reduced ID Numbers

網址

http://poj.org/problem?id=2769

題意

t個測資 給n個數字 找出最小的數字m,使得每個數字%m的value皆不同

Technique details

input

::

2
1
124866
3
124866
111111
987651

output

::

1
8

演算法

任兩個數字a,b

令 D= a,b 的差值

若 a,b %M 的 value 是一樣的

則 a,b %( M 的所有因數 ) 的 value 也是一樣的

所以只要枚舉任兩個數字,取得差值,把差值的所有因數都去掉,

找出最小的 m 即可。