【模板】数论板子
2022/6/7 23:21:17
本文主要是介绍【模板】数论板子,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
数论分块
用于求解
\[\sum\limits_{i=1}^{n}f_i\cdot \left\lfloor\dfrac{n}{i}\right\rfloor \]亦可求解多维
\[\sum\limits_{i=1}^{\min(n_1,n_2,\cdots,n_k)}(f_i\cdot \prod\limits_{j=1}^{k}\left\lfloor\dfrac{n_j}{i}\right\rfloor) \]前提是求出了数论函数\(f(n)\)的前缀和。
ull NTSD(ull pre[],int n) { //number-theory; //sqrt-decomposition; int l = 1, r = 0; ull result = 0; while(l <= n) { r = (int)floor(n/floor(1.0*n/l)); result += (pre[r]-pre[l-1])*1ll*floor(n/l); l = r+1; } return result; } ull NTSDQ(ull pre[],int n,int m) { int l = 1, r = 0; ull result = 0; while(l <= min(m,n)) { r = (int)min(n/(1.0*n/l),m/(1.0*m/l)); result += (pre[r]-pre[l-1])*1ll*(n/l)*(m/l); l = r+1; } return result; }
筛法
\(prime,\varphi(n),\mu(n)\)
int mu[z]; bitset<z> b; ull prime[z]; ull phi[z]; ull minp[z]; void line_prime(int n) { b.reset(); for(int i = 2;i <= n;++i) { if(!b[i]) prime[++prime[0]] = i; for(int j = 1;j <= prime[0];++j) { if(i*prime[j] > n) break; if(!minp[i*prime[j]]) minp[i*prime[j]] = prime[j]; b[i*prime[j]] = 1; if(i%prime[j] == 0) break; } } } void line_phi(int n) { b.reset(); phi[1] = 1; for(int i = 2;i <= n;++i) { if(!b[i]) { prime[++prime[0]] = i; phi[i] = i-1; } for(int j = 1;j <= prime[0];++j) { if(i*prime[j] > n) break; if(i%prime[j]) phi[i*prime[j]] = phi[i]*phi[prime[j]]; else { phi[i*prime[j]] = phi[i]*prime[j]; break; } } } } void line_mu(int n) { b.reset(); mu[1] = 1; for(int i = 2;i <= n;++i) { if(!b[i]) { mu[i] = -1; prime[++prime[0]] = i; } for(int j = 1;j <= prime[0];++j) { if(i*j > n) break; b[i*prime[j]] = 1; if(i%prime[j] == 0) { mu[i*prime[j]] = 0; break; } mu[i*prime[j]] = -mu[i]; } } } ull tau[z], sigma; ull num[z]; void line_tau(int n) { tau[1] = 1; for(int i = 2;i <= n;++i) { if(!b[i]) { b[i] = 1; prime[++prime[0]] = i; tau[i] = 2; num[i] = 1; } for(int j = 1;j <= prime[0];++j) { if(i*prime[j] > n) break; b[i*prime[j]] = 1; if(i%prime[j] == 0) { num[i*prime[j]] = num[i]+1; tau[i*prime[j]] = tau[i]/num[i*prime[j]]*(num[i*prime[j]]+1); break; } else { num[i*prime[j]] = 1; tau[i*prime[j]] = tau[i]*2; } } } }
这篇关于【模板】数论板子的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门:从零开始的编程之旅
- 2024-11-23Java创业入门:新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门:初学者的简单教程
- 2024-11-23JAVA副业入门:初学者的实战指南