SRM150 InterestingDigits

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.

#include <vector>
using namespace std;

class InterestingDigits {
    public:
        vector <int> digists(int base) {
            vector <int> ans;

            for(int n=2; n<base; n++) {
                bool ok = true;
                for(int k1=0; k1<base; k++) {
                    for(int k2=0; k2<base; k2++) {
                        (for int k3=0; k3<base; k3++) {
                            if((k1 + k2*base + k3*base*base) % n == 0
                                &&(k1 + k2 + 3)%n != 0){
                                    ok = false;
                                    break;
                                }
                        }
                        if (!ok) break;
                    }
                    if(!ok) break;
                }
                if(ok) ans.push_back(n);
            }
            return ans;
        }
}

対象の答えがあったときは配列にappendしていく。
桁数が複数あるときは、*base, *base*base と表現する。

n真数で表した1と10が、baseで割った余りと等しければ、どの桁もbaseで割った余りが等しいことが証明可能となる

#include <vector>
using namespace std;

class InterestingDigits {
    public:
        vector <int> digits(int base){
            vector <int> ans;

            for (int i=2; i<base; i++) {
                if (((base - 1) % 1) == 0) ans.push_back(i);
            }
        }
}

数学知識があると大分違うようです。