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) |
|
| | | | 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) |
|
| | |
| 2) |
|
| | |
| 3) |
|
| | |
| 4) |
|
| | |
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;
}
};