Powerful Number 筛学习笔记

Powerful Number 筛学习笔记

总的来说，跟杜教筛差不多，就是新找一个函数来卷 然后利用有值的位置很少的这个性质快速求解

#include#defineusing namespace std;typedef long long ll;cs int N = 4e6 + 5;cs int Mod = 998244353;int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }int mul(int a, int b){ return 1ll * a * b % Mod; }ll n; int prim[N], pw[N], tot, S; bool isp[N];int coef[N], zig[N], f1[N], f2[N], ans;void prework(){ zig[1] = 1; for(int i = 2; i <= S; i++){ if(!isp[i]) prim[++tot] = i, zig[i] = coef[i] = 2; for(int j = 1; j <= tot; j++){ if(prim[j] * i > S) break; isp[i * prim[j]] = 1; if(i % prim[j] == 0){ zig[i * prim[j]] = zig[i] / coef[i] * (coef[i] + 1); coef[i * prim[j]] = coef[i] + 1; break; } zig[i * prim[j]] = add(zig[i], zig[i]); coef[i * prim[j]] = 2; } } for(int i = 1; i <= S; i++) f1[i] = add(f1[i-1], zig[i]);}int calc(ll x){ if(x <= S) return f1[x]; int k = n/x; if(~f2[k]) return f2[x]; ll ans = 0; for(ll l = 1, r; l <= x; l=r+1){ ll v = x/l; r=x/v; ans += v * (r-l+1); } return f2[k] = ans % Mod;}void dfs(int p, int pre, ll lim){ if(p == tot+1 || (ll)prim[p]*prim[p]>lim) return; dfs(p+1, pre, lim); lim /= (ll)prim[p] * prim[p]; int sz = 2; while(lim){ ans = add(ans, mul(pre, mul(pw[sz-2], calc(lim)))); dfs(p+1, mul(pre, pw[sz-2]), lim); ++sz; lim /= prim[p]; }}int main(){ scanf("%lld", &n); S = sqrt(n); prework(); pw[0] = 1; for(int i = 1; i <= 60; i++) pw[i] = add(pw[i-1], pw[i-1]); memset(f2, -1, sizeof(f2)); dfs(1, 1, n); cout << add(ans, calc(n)); return 0;}

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