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

            ArcTan

            dfs
            隨筆 - 16, 文章 - 117, 評論 - 6, 引用 - 0
            數據加載中……

            SRM 150 DIV 2 500pt(thinking && 數論)

            Problem Statement

                

            The digits 3 and 9 share an interesting property. If you take any multiple of 3 and sum its digits, you get another multiple of 3. For example, 118*3 = 354 and 3+5+4 = 12, which is a multiple of 3. Similarly, if you take any multiple of 9 and sum its digits, you get another multiple of 9. For example, 75*9 = 675 and 6+7+5 = 18, which is a multiple of 9. Call any digit for which this property holds interesting, except for 0 and 1, for which the property holds trivially.

            A digit that is interesting in one base is not necessarily interesting in another base. For example, 3 is interesting in base 10 but uninteresting in base 5. Given an int base, your task is to return all the interesting digits for that base in increasing order. To determine whether a particular digit is interesting or not, you need not consider all multiples of the digit. You can be certain that, if the property holds for all multiples of the digit with fewer than four digits, then it also holds for multiples with more digits. For example, in base 10, you would not need to consider any multiples greater than 999.

            Definition

                
            Class: InterestingDigits
            Method: digits
            Parameters: int
            Returns: vector <int>
            Method signature: vector <int> digits(int base)
            (be sure your method is public)
                

            Notes

            - When base is greater than 10, digits may have a numeric value greater than 9. Because integers are displayed in base 10 by default, do not be alarmed when such digits appear on your screen as more than one decimal digit. For example, one of the interesting digits in base 16 is 15.

            Constraints

            - base is between 3 and 30, inclusive.

            Examples

            0)
                
            10
            Returns: { 3,  9 }
            All other candidate digits fail for base=10. For example, 2 and 5 both fail on 100, for which 1+0+0=1. Similarly, 4 and 8 both fail on 216, for which 2+1+6=9, and 6 and 7 both fail for 126, for which 1+2+6=9.
            1)
                
            3
            Returns: { 2 }

            2)
                
            9
            Returns: { 2,  4,  8 }

            3)
                
            26
            Returns: { 5,  25 }

            4)
                
            30
            Returns: { 29 }

            This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.


            題意給定base進制數里,找出里面所有的特別的數x,對于x的倍數kx,它的每一位的和還是x的倍數。
            比如base=10,則x=3和9。

            這個應該是小學時候就記得的結論了,專門算3和9的,哈哈。

            結論:base %x==1是充要條件。
            證明:
                           a=a1*base^0+a2*base^1+a3*base^2,對于任何a都可以這樣分解
                    因為 base % x=1,則base^k %x==1。則上式化簡為
                           a==a1+a2+a3+.. (mod x)
                     反之,也可得base %x==1

            440PT啊,小小猶豫了下哦。直接枚舉了x驗證啊。

            其實就是求base-1的因子,如果base很大地話,是不能這樣去枚舉的。因子分解哦,又是經典問題啊。

            #include<stdio.h>
            #include
            <string.h>
            #include
            <vector>
            #include
            <algorithm>
            using namespace std;

            class InterestingDigits{
            public:
                vector 
            <int> digits(int base){
                    
            int a[31];
                    
            int n=0;
                    
            int i=2;
                    
            while (i<base){
                        
            if (base % i==1)
                            a[n
            ++]=i;
                        i
            ++;
                    }
                    vector 
            <int> ans(n);
                    
            for (i=0;i<n;i++)
                        ans[i]
            =a[i];
                    
            return ans;
                }
            };



            posted on 2012-07-15 21:54 wangs 閱讀(258) 評論(0)  編輯 收藏 引用 所屬分類: ACM-數學Topcoder

            91精品国产91久久综合| 久久伊人精品青青草原高清| 日本久久中文字幕| 亚洲综合日韩久久成人AV| 少妇无套内谢久久久久| 久久天天躁狠狠躁夜夜avapp| 久久91精品国产91久久麻豆| 亚洲欧美国产精品专区久久| av国内精品久久久久影院 | 99久久婷婷国产综合精品草原| 久久久久亚洲AV无码专区桃色| 亚洲AV无码久久精品狠狠爱浪潮| 久久福利青草精品资源站免费| 中文字幕精品久久久久人妻| 久久精品www| 婷婷久久久亚洲欧洲日产国码AV| 国产精品99久久久久久猫咪| 久久99精品国产麻豆| 精品人妻伦九区久久AAA片69| 99久久精品这里只有精品| 人妻少妇久久中文字幕| 狠狠人妻久久久久久综合| 中文字幕日本人妻久久久免费 | 色偷偷888欧美精品久久久| 蜜臀久久99精品久久久久久小说 | 久久人妻少妇嫩草AV无码专区| 久久久亚洲精品蜜桃臀| 久久青草国产精品一区| 男女久久久国产一区二区三区| 超级97碰碰碰碰久久久久最新| 久久精品无码一区二区三区免费| 色成年激情久久综合| 久久精品一区二区国产| 99久久精品毛片免费播放| 无码专区久久综合久中文字幕| 狠狠综合久久综合88亚洲 | 亚洲国产成人久久综合一 | 久久本道伊人久久| 精品久久久久久国产| 久久久一本精品99久久精品88 | 久久香综合精品久久伊人|