close
題目概要：
給一個F(n)滿足以下條件：
1. n%10 if(n%10>0)
2. 0 if(n=0)
3. F(n/10) otherwise。
計算出p~q的總和。
解題方向：
1. 不可以直接依題目所給的條件寫成遞迴or迴圈，因為這樣執行時間會超過。雖然輸入是32bit，不過加總後的答案可能會超過32bit。
2. 使用(1+2+...+q)-(1+2+...+p)的概念。
3. 計算有多少個10的倍數(因為1+2+3+..+9=45，可以直接個數*45)，加上剩下的數字(10的餘數)。
4. 當數字<=0時終止迴圈。
程式碼：
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| //Java | |
| import java.util.Scanner; | |
| class uva10994{ | |
| public static void main(String args[]){ | |
| Scanner sc=new Scanner(System.in); | |
| long p=0,q=0; | |
| while(sc.hasNext() && (p=sc.nextLong())>=0 && (q=sc.nextLong())>=0){ | |
| long sum=0; | |
| p--; | |
| //計算sum-1~(p-1)的總和 | |
| while(p>0){ | |
| /* | |
| 1. 1+2+3+...+9=45。 | |
| 2. 1+2+...+n=n*(n+1)/2 ps.可以想成1+2+...+n會有幾個n，剛好會是(n+1)/2個。 | |
| 3. 除10(有多少10的倍數)，取10餘數(剩下的數字)。 | |
| 4. 當數字小於0終止迴圈。 | |
| Ex p=1 q=214 | |
| */ | |
| sum=sum-(p/10)*45-(p%10+1)*(p%10)/2; | |
| p=p/10; | |
| } | |
| //計算sum+1~q的總和 | |
| while(q>0){ | |
| sum=sum+(q/10)*45+(q%10+1)*(q%10)/2; | |
| q=q/10; | |
| } | |
| //結果輸出 | |
| System.out.println(sum); | |
| } | |
| } | |
| } |
文章標籤
全站熱搜
留言列表
