• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            pku1309 數學優化+枚舉

            題目
            Coconuts, Revisited
            Time Limit: 1000MS
            Memory Limit: 10000K
            Total Submissions: 1832
            Accepted: 737

            Description

            The short story titled Coconuts, by Ben Ames Williams, appeared in the Saturday Evening Post on October 9, 1926. The story tells about five men and a monkey who were shipwrecked on an island. They spent the first night gathering coconuts. During the night, one man woke up and decided to take his share of the coconuts. He divided them into five piles. One coconut was left over so he gave it to the monkey, then hid his share and went back to sheep.

            Soon a second man woke up and did the same thing. After dividing the coconuts into five piles, one coconut was left over which he gave to the monkey. He then hid his share and went back to bed. The third, fourth, and fifth man followed exactly the same procedure. The next morning, after they all woke up, they divided the remaining coconuts into five equal shares. This time no coconuts were left over.

            An obvious question is "how many coconuts did they originally gather?" There are an infinite number of answers, but the lowest of these is 3,121. But that's not our problem here.

            Suppose we turn the problem around. If we know the number of coconuts that were gathered, what is the maximum number of persons (and one monkey) that could have been shipwrecked if the same procedure could occur?

            Input

            The input will consist of a sequence of integers, each representing the number of coconuts gathered by a group of persons (and a monkey) that were shipwrecked. The sequence will be followed by a negative number.

            Output

            For each number of coconuts, determine the largest number of persons who could have participated in the procedure described above. Display the results similar to the manner shown below, in the Expected Output. There may be no solution for some of the input cases; if so, state that observation.

            Sample Input

            25 30 3121 -1

            Sample Output

            25 coconuts, 3 people and 1 monkey 30 coconuts, no solution 3121 coconuts, 5 people and 1 monkey

            Source


            解法:
            首先寫出遞推公式
            f(0)=A  A=nk
            f(i)=f(i-1)/(n-1)*n+1

            隨便什么方法寫出閉形式
            f(n)=[(n^n)*(A+n-1)]/[(n-1)^n]-(n-1)
            題目中告訴f(n)的值,求n最大值
            首先觀察下前面那個分式,由于n和n-1互質,所以n^n和(n-1)^n也互質,分式結果要為一個整數,f(n)+n-1中必須含有因子n^n;換句話說,f(n)+n-1>n^n,題目中給的f(n)可以用32位整數表示,那么n必然小于12!
            下面不用說什么了,暴力吧,肯定0MS了~不過為了完美,n^n我用了二進制快速冪~具體看代碼吧

            代碼:
             1 Source Code
             2 Problem: 1309        User: yzhw
             3 Memory: 392K        Time: 0MS
             4 Language: G++        Result: Accepted
             5 
             6     Source Code
             7 
             8     # include <cstdio>
             9     using namespace std;
            10     long long pow(int a,int b)
            11     {
            12         long long ans=1,t=a;
            13         while(b)
            14         {
            15             if(b&1) ans*=t;
            16             t*=t;
            17             b>>=1;
            18         }
            19         return ans;
            20     }
            21     int main()
            22     {
            23         //freopen("input.txt","r",stdin);
            24         int n;
            25         while(scanf("%d",&n)!=EOF&&n>=0)
            26         {
            27             int ans=-1,i;
            28             for(i=2;i<=12;i++)
            29             {
            30                 long long t=n;
            31                 t+=i-1;
            32                 long long t1=pow(i,i),t2=pow(i-1,i);
            33                 if(t%t1==0)
            34                 {
            35                     t=t/t1*t2-i+1;
            36                     if(t>=0&&t%i==0) ans=i;
            37                 }
            38             }
            39             if(ans==-1) printf("%d coconuts, no solution\n",n);
            40             else printf("%d coconuts, %d people and 1 monkey\n",n,ans);
            41         }
            42         return 0;
            43     }
            44 
            45 

            posted on 2011-07-19 00:10 yzhw 閱讀(233) 評論(0)  編輯 收藏 引用 所屬分類: numberic

            <2010年11月>
            31123456
            78910111213
            14151617181920
            21222324252627
            2829301234
            567891011

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            日产精品久久久久久久| 日产精品久久久久久久| 色成年激情久久综合| 久久电影网一区| 久久激情五月丁香伊人| 久久综合亚洲鲁鲁五月天| 无码伊人66久久大杳蕉网站谷歌| 亚洲精品高清国产一线久久| 久久精品国产69国产精品亚洲| 久久久久亚洲AV综合波多野结衣| 性做久久久久久久| 欧美久久综合九色综合| 久久中文骚妇内射| 伊人久久一区二区三区无码| 久久精品国产亚洲精品2020| 要久久爱在线免费观看| 97久久久久人妻精品专区| 中文字幕无码久久久| 国产成人久久精品二区三区| 亚洲精品国精品久久99热一| 久久性精品| 国产亚州精品女人久久久久久 | 久久精品国产一区二区| 色综合久久无码中文字幕| 亚洲AⅤ优女AV综合久久久| 久久精品国产亚洲沈樵| 久久久久人妻一区精品色| 精品久久久久久久久免费影院| 国产精品99久久久久久www| 精品久久久久久国产| 国产午夜精品久久久久免费视| 亚洲精品无码久久久影院相关影片| 久久久久久国产a免费观看不卡| 日韩欧美亚洲综合久久影院d3| 成人免费网站久久久| 久久精品国产亚洲麻豆| 91超碰碰碰碰久久久久久综合| 狠色狠色狠狠色综合久久| 91精品国产91热久久久久福利 | 久久综合亚洲欧美成人| 国产成人久久精品一区二区三区|