题解 CF1139D 【Steps to One】

officeyutong

2019-03-31 13:45:56

Solution

怎么各位dalao的复杂度都不是$O(m)$啊...瑟瑟发抖qwq ![](https://cdn.luogu.com.cn/upload/pic/55533.png) ```cpp #include <cstring> #include <iostream> using int_t = long long int; using std::cin; using std::cout; using std::endl; const int_t mod = 1e9 + 7; const int_t LARGE = 1e5; int_t inv[LARGE + 1]; int_t m; int_t mu[LARGE + 1]; int_t factor[LARGE + 1]; bool isPrime[LARGE + 1]; int main() { memset(isPrime, 1, sizeof(isPrime)); cin >> m; inv[1] = 1; for (int_t i = 2; i <= m; i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod; for (int_t i = 2; i <= m; i++) if (isPrime[i]) { for (int_t j = i * i; j <= m; j += i) { factor[j] = i; isPrime[j] = false; } factor[i] = i; } mu[1] = 1; for (int_t i = 2; i <= m; i++) { int_t p = factor[i]; if (i / p % p == 0) mu[i] = 0; else mu[i] = mu[i / p] * -1; } int_t result = 1; for (int_t i = 2; i <= m; i++) { int_t x = m / i; result = (result - mu[i] * x % mod * inv[m - x] % mod + mod) % mod; } cout << result << endl; return 0; } ```