gcd数论分块

gcd数论分块

#include #include #include#includeusing namespace std;typedef long long ll;const int N = 3e6 + 10;const int mod = 998244353;const double eps = 1e-6;int n;ll l[N], r[N];ll c[N], cnt0[N];ll inv[N], v[N];double d[N];ll qmi (ll a, ll b, ll c) { ll ans = 1; while (b) { if (b & 1) ans = ans * a % c; a = a * a % c; b >>= 1; } return ans;} int main () { cin >> n; for(int i=0;i<=300000;i++) c[i]=1; for(int i=1;i<=300000;i++)d[i]=1.0000000000001l/i; for (int i = 1; i <= 300000; i ++) inv[i] = qmi(i, mod - 2, mod); for (int i = 1; i<= n; i ++) { cin >> l[i] >> r[i]; cnt0[r[i] + 1] ++; for (ll j = 1, t = l[i] - 1, T = r[i], k = 0; j <= T ; j = k + 1) { //ll x = t * d[j] , y = T * d[j] ; ll x = t * inv[j] % mod, y = T * inv[j] % mod; if (x) k = min(t * d[x], T * d[y] ); else k = T * d[y]; ll u = y - x; if (!u) cnt0[j] ++, cnt0[k + 1] --; else { c[j] = c[j] * u % mod, c[k + 1] = c[k + 1] * inv[u] % mod; } } } ll ans = 0; for (ll i = 1; i <= 300000; i ++) { cnt0[i] += cnt0[ i -1]; (c[i] = c[i] * c[i - 1] % mod) ; if (!cnt0[i]) ans = (ans + c[i]) % mod; } cout << ans << endl; return 0;}

数论分块。这题求的各种可能序列的约数的和。由此我们可以直接枚举约数，然后计算他对某个区间的贡献 O（n * sqrt(n)）。注意这里求数量的时候不能用逆元，否则会段错误。需要手动处理1 / i https://ac.nowcoder.com/acm/contest/11185/D

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。