Re: [問題] 懇請協助設計C語言程式

[yauhh (喲)]

※ 引述《ksjksj (法輪大法好)》之銘言：
: f(n)=(a+1)^n-(a)^n必為奇數,a,n為自然數
: a=1,...1000
: n=1,...1000
: 這個問題我想了兩週
: 網路上也沒有現成的程式碼可套用
: 懇請高手協助 不勝感荷


bool property_f(uint a, uint n) {
        return ((int)pow(a+1, n) - (int)pow(a, n)) % 2 != 0;

}

     bool check = true;
     for (a = 1; a<= 1000; a++) for(n = 1; n<=1000; n++)
        check = check && property_f(a, n);

check 就是答案.

但是,如果 n 是 0, (a+1)^0 - a^0 = 1 - 1 = 0, 奇數?? 怎麼解?
就不要連 a 也是 0, 你就不知道怎麼算 0^0.

=== 補充 ===
我發現問題在哪了... 檢查1000^1000很麻煩,還要處理大數...

不過,看到 (a+1)^n 很容易想到 http://en.wikipedia.org/wiki/Binomial_theorem
f(a,n) 可以轉成 c_n*a^(n-1)*1^1 + c_(n-1)*a^(n-2)*1^2 + ... + c_0*a^0*1^n.
那你就要把先討論 a^n when a=1..1000, n=1..1000 是奇數偶數,
然後再想任何 x * y * z, x y z 各怎樣的時候會得到奇數,又怎樣會得到偶數.
最後再想一連串奇數或偶數相加,它們是不是都加總為奇數.

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.112.230.54
※ 編輯: yauhh           來自: 59.112.230.54        (10/29 03:39)
→ tropical72:題意已有限制,a,n!=0,但a,n=1000時,pow似乎會爆
→ yauhh:題意是有限制,但是畢竟"自然數"三字一出,思考中就要把0順便
→ yauhh:想一想.
推 ledia:double 有誤差, 直接 case int 會錯
→ ledia:正解上一篇已經說過了
推 ledia:若一邊取 % 一邊乘, 並 resue 之前結果, 比 pow 來得快
→ ledia:s/case/cast/
推 ledia:其實不光是誤差會錯, 光數值 overflow, cast 回來就不對了
→ yauhh:沒有人會想自己弄出overflow
→ yauhh:遇到overflow是一定會修正的,再講一次,這是討論不是解題服務
推 ledia:你的做法也沒解到題啊 XD