天天看點

【JZOJ4934】【NOIP2017GDKOI模拟1.12】ahelplessfuckingBitch Man

helpless

【JZOJ4934】【NOIP2017GDKOI模拟1.12】ahelplessfuckingBitch Man

fucking

結論:如果一個數可以被對于a序列中每個數的最大公約數整除,那麼它就是好的。

Bitch Man

感性證明:

貪心地想,對于a序列中的任意兩個數,它們的最大公約數可由這兩個數相減得到。

而且顯然這個最大公約數完全可以替代掉原來的兩個數并成為a序列中的一個新的元素。

這個新的元素就可以和其他元素繼續取最大公約數。

給所有數取個最大公約數,這個最大公約數會替代掉整個a序列中的所有元素。

轉載于:https://www.cnblogs.com/hiweibolu/p/6714808.html