• <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 閱讀(257) 評論(0)  編輯 收藏 引用 所屬分類: ACM-數學Topcoder

            99久久精品免费看国产一区二区三区| 人妻无码αv中文字幕久久琪琪布| 精品蜜臀久久久久99网站| 欧美一区二区三区久久综| 精品久久久久久久久中文字幕| 国产69精品久久久久9999| 国产激情久久久久久熟女老人 | 久久国产热精品波多野结衣AV| 国产成年无码久久久久毛片| 精品无码人妻久久久久久| 99久久无色码中文字幕人妻| 99久久成人18免费网站| 久久99精品国产自在现线小黄鸭| 精品久久久久久无码中文野结衣 | 久久频这里精品99香蕉久| 99久久国产热无码精品免费| 亚洲国产高清精品线久久| 国内精品久久国产大陆| 99久久99久久精品国产片果冻 | 久久精品9988| 热re99久久精品国99热| 中文字幕亚洲综合久久菠萝蜜| 亚洲欧美精品伊人久久| 久久久久免费看成人影片| 久久精品国产免费观看三人同眠| 丰满少妇人妻久久久久久4| 久久精品国产精品青草| 九九精品99久久久香蕉| 久久久亚洲欧洲日产国码二区 | 久久AV高潮AV无码AV| 日韩欧美亚洲国产精品字幕久久久| 免费观看久久精彩视频| 国产精品欧美久久久天天影视| 色综合久久中文字幕无码| 中文无码久久精品| 亚洲人成网亚洲欧洲无码久久| 久久久久久免费视频| 狠狠色丁香久久婷婷综合_中 | 久久SE精品一区二区| 久久精品亚洲AV久久久无码| 久久婷婷五月综合国产尤物app|