数论|欧拉定理

lc

lc3463

对数字字符串重复执行“相邻数字和模10替换原字符”的操作，直到只剩两个数字，判断这两个数字是否相同。

解法:

预处理阶乘、逆元及因子2和5的计数，用组合数计算字符串相邻字符差值的加权和

判断其模10是否为0，以此验证字符串是否符合特定数字特征

const int MOD = 10;

const int MX = 100'000;

array<int, MX + 1> f, inv_f, p2, p5;

int qpow(int x, int n) {

int res = 1;

while (n > 0) {

if (n % 2 > 0) {

res = res * x % MOD;

}

x = x * x % MOD;

n /= 2;

}

return res;

}

auto init = []() {

f[0] = inv_f[0] = 1;

for (int i = 1; i <= MX; i++) {

int x = i;

// 计算 2 的幂次

int e2 = countr_zero((unsigned) x);

x >>= e2;

// 计算 5 的幂次

int e5 = 0;

while (x % 5 == 0) {

e5++;

x /= 5;

}

f[i] = f[i - 1] * x % MOD;

inv_f[i] = qpow(f[i], 3); // 欧拉定理求逆元

p2[i] = p2[i - 1] + e2;

p5[i] = p5[i - 1] + e5;

}

return 0;

}();

int comb(int n, int k) {

// 由于每项都 < 10，所以无需中途取模

return f[n] * inv_f[k] * inv_f[n - k] *

qpow(2, p2[n] - p2[k] - p2[n - k]) *

qpow(5, p5[n] - p5[k] - p5[n - k]) % MOD;

}

class Solution {

public:

bool hasSameDigits(string s) {

int diff = 0;

for (int i = 0; i + 1 < s.size(); i++) {

diff += comb(s.size() - 2, i) * (s[i] - s[i + 1]);

}

return diff % MOD == 0;

}

};