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

            国产精品免费福利久久| 热综合一本伊人久久精品| 久久精品?ⅴ无码中文字幕| 久久影视综合亚洲| 天堂久久天堂AV色综合| 国内精品久久久久久久久| 久久久亚洲欧洲日产国码二区| 久久久久亚洲AV成人网人人软件| 人妻无码αv中文字幕久久琪琪布| 久久精品青青草原伊人| 国内精品伊人久久久久网站| 亚洲欧美成人久久综合中文网| 国产精品久久久久影院嫩草| 一极黄色视频久久网站| 狠狠色丁香久久综合婷婷| 久久一日本道色综合久久| 少妇内射兰兰久久| 色婷婷久久久SWAG精品| 久久久久免费精品国产| …久久精品99久久香蕉国产| 三级韩国一区久久二区综合| 久久免费高清视频| 无码人妻久久一区二区三区免费| 日本高清无卡码一区二区久久| 久久综合狠狠综合久久激情 | 色综合久久中文综合网| 亚洲精品国产美女久久久| 亚洲国产成人精品91久久久| 久久精品亚洲欧美日韩久久| 99久久国产主播综合精品| 久久中文娱乐网| 久久亚洲国产午夜精品理论片| 久久精品九九亚洲精品| 久久精品水蜜桃av综合天堂| 伊人久久大香线蕉综合影院首页| 久久精品国产2020| 久久久久久久精品妇女99| 国内精品久久久久影院薰衣草| 亚洲欧美精品一区久久中文字幕| 久久久久国产| 久久久久久国产a免费观看黄色大片 |