Untitled

 avatar
unknown
plain_text
2 months ago
1.0 kB
8
Indexable
class Solution {
    int mypow(int a, int b, int m) {
        int re = 1;
        while (b) {
            if (b & 1) re = re * a % m;
            b >>= 1, a = a * a % m;
        }
        return re;
    }
public:
    bool f(string s, int m) {
        int n = s.size();
        vector<int> p(n), d(n, 1), c(n), a(n, 1), rev(m, 1);
        for (int i = 1; i < m; i++) rev[i] = mypow(i, m - 2, m);

        for (int i = 1; i < n; i++) {
            if (i % m)
                d[i] = i % m;
            else
                p[i] = p[i / m] + 1, d[i] = d[i / m];
        }
        for (int i = 1; i + 1 < n; i++) {
            c[i] = c[i - 1] + p[n - 1 - i] - p[i];
            a[i] = a[i - 1] * d[n - 1 - i] * rev[d[i]] % m;
        }

        int all = 0;
        for (int i = 0; i + 1 < n; i++) {
            if (c[i] == 0) {
                all += (s[i] - s[i + 1]) * a[i];
            }
        }
        return all % m == 0;
    }
    bool hasSameDigits(string s) {
        return f(s, 2) && f(s, 5);
    }
};
Editor is loading...
Leave a Comment