• <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

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            国产精品久久自在自线观看| 五月丁香综合激情六月久久| 欧美丰满熟妇BBB久久久| 久久久久久精品无码人妻| 亚洲国产精品久久久天堂| 久久精品亚洲精品国产色婷| 久久香蕉一级毛片| 久久亚洲国产精品五月天婷| 国产精品久久久久久久人人看| 性做久久久久久久| 青青草国产精品久久久久| 久久婷婷色综合一区二区| 无码日韩人妻精品久久蜜桃| 国产精品伦理久久久久久| 久久久久国产精品人妻| 国产精品欧美久久久久天天影视| 欧美午夜A∨大片久久| 99久久成人国产精品免费| 香蕉aa三级久久毛片| 色综合合久久天天综合绕视看| 一级做a爰片久久毛片看看| 久久精品国产亚洲沈樵| 国产精品美女久久福利网站| 久久国产精品久久国产精品| 亚洲精品无码专区久久久| 亚洲国产成人久久精品99 | 久久亚洲春色中文字幕久久久 | 久久频这里精品99香蕉久| 国产精品免费福利久久| 2021国产精品久久精品| 久久精品国产亚洲AV不卡| 国产一级做a爰片久久毛片| 中文字幕热久久久久久久| 久久久久亚洲国产| 亚洲AV伊人久久青青草原| 99久久精品国产综合一区| 国产成人久久激情91| 国产精品久久久久久一区二区三区| 久久精品一区二区三区AV| 日产精品久久久久久久| 久久久久久精品成人免费图片|