107 - The Cat in the Hat

Sylveon

原題：http://luckycat.kshs.kh.edu.tw/homework/q107.htm
ACCODE :

2006/09/02 Sat 17:03:34
副版(gloompisces)好像一直尸位素餐，來貼點東西好了

這題是math題，我推的公式好像不太好，似乎有更簡單的

設題目給你的兩個數是a和b，你要求出p,q，使

p^q=a
(p-1)^q=b

輸出c和d。

分別是
c = 1 + (p-1) + (p-1)^2 +...+ (p-1)^(q-1)
d = [p^q * (p-1)^0] + [p^(q-1) * (p-1)^1] + .... + [p^0 * (p-1)^q]

以第一組測資為例，216 = 6^3 ，125 = 5^3
所以
c = 1+5+25=31
d = 1*216 + 5*36 + 25*6 + 125*1 = 671


<求 c d>
用等比級數
c = 1 + (p-1) + (p-1)^2 +...+ (p-1)^(q-1)
公比為 p-1，首項為 1
  = (1) * [(p-1)^q - 1]/[(p-1) - 1]
以 (p-1)^q = b 代入
c = (b-1) / (p-2)

d = [p^q * (p-1)^0] + [p^(q-1) * (p-1)^1] + .... + [p^0 * (p-1)^q]
公比為 (p-1)/p，首項為 p^q
  = (p^q) * {[(p-1)/p]^(q+1) - 1} / [(p-1)/p - 1]
化簡)^q = b故
  = (p-1)^(q+1) - p^(q+1) = (p-1)*[(p-1)^q] - p*[p^q]
以 a = p^q ，(p-1)^q = b 代入
d = (p-1)*b - p*a

<求 a b>
以 (p-1)+1 = p 代入a,展開
a = p^q
  = [(p-1)+1]^q
  = (p-1)^q + ...(中間這幾項皆有因數p-1)... + 1^q

(p-1)^q = b故
  p-1 | a-b-1
  p-1 | b

所以 p-1 | gcd(b,a-b-1)

特別注意當 a-b-1 = 0 時不成立 (RE 了好幾次 >_<)，要另外做

還有 a = p^q，所以 p | a

從最大gcd(b,a-b-1)因數的開始找，直到 p | a 成立

我猜這是正解(證不出來)，但為了保險起見，由

log_p(a) = loq_(p-1)(b)

加上

log(a)/log(b) = log(p)/log(p-1)

來檢驗







作者  sa072686
時間  2007/03/05 Mon 19:11:24

卡好久的數學題…後來發現還蠻暴力的

0.293sec AC，373/2607

解法…嗯，在下面

設開始貓的高度為n，最後工作的貓有m隻

可知必存在i使得(i+1)^j == n，i^j == m

由此可知i必為m之因數且i<sqrt(m)或者特例，即i == m

否則無法找到j使得i^j == m，之後對可能的i做檢查

若可找到一j使得i^j == m則試試(i+1)^j是否等於n，如是則此i為正解

反之則繼續，想必若i和j找到後要求答案便不困難，故不再贄述