Untitled
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