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

版本 faea53e83e3eb4c2892930aa35ae5d1b01935640

contest/acm/POJ/2769

Changes from faea53e83e3eb4c2892930aa35ae5d1b01935640 to ac6cbde002168759c3742b501bd8d1098bc6dc30

---
title: POJ 2769
toc: no
categories: 題解
categories: 題解 數論
...

網址
====

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

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

Technique details
=================

input
-----

2
1
124866
3
124866
111111
987651
::

    2
    1
    124866
    3
    124866
    111111
    987651

output
------

1
8
::

    1
    8

演算法
======

任兩個數字a,b

令 D= a,b 的差值

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

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

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

找出最小的 m 即可。