首页 > 其他分享 >多项式

多项式

时间:2024-05-13 12:40:56浏览次数:20  
标签:筛求 积性 多项式 void int 欧拉

积性函数

1.利用欧拉筛求f(1),……,f(n)

//欧拉筛求f(1),……,f(n)
void euler{
	f[1]=1;
	for(int i=2;i<=n;i++){
		if(!st[i]) p[++tot]=i,f[i]=calc_f(i,1);
		for(int j=1;j<=tot&&i*p[j]<=n;j++){
			st[i*p[j]]=true;
			if(i%p[j]==0){
				cnt[i*p[j]]=cnt[i]+1;//cnt[n]:表示n的最小的质因子出现的次数
				f[i*p[j]]=f[i]/calc_f(p[j],cnt[i])*calc_f(p[j],cnt[i]+1);//对p[j]的出现次数进行一个修正 
			}
			cnt[i*p[j]]=1;//i*p[j]的最小质因子为p[j],并且出现次数为1
			f[i*p[j]]=f[i]*calc_f(p[j],1); 
		}
	} 	
}

标签:筛求,积性,多项式,void,int,欧拉
From: https://www.cnblogs.com/mendax-Z/p/18188994

相关文章

  • [多项式] FFT小计
    引入给出两个多项式\(A,B\),计算它们相乘的结果。我们能轻易写出code:for(inti=0;i<=n;i++) for(intj=0;j<=n;j++) C[i+j]+=A[i]*B[j];然后超时了。FFT是一种将多项式乘法优化成\(O(n\logn)\)的神仙算法。分析上面的式子没有任何优化空间。什么意思呢?就是怎......
  • 多项式板子
    本页面由洛谷云剪贴板进化而来。免责:多项式可能未经良好测试,并不完善或可能执行时出现问题,如有问题请在本页评论区说明。改自Submission。备份。feature:指令集优化ntt(来自fjzzq2002);转置原理多点求值与插值;2log多项式复合(逆)(改自hly1204github版);开罐即食版多叉半在线卷积......
  • 多项式计数
    注:其实前面还有一些内容,如矩阵树定理一类的东西。但是由于我还没有整理好所以把整理好的部分弄上来。一些DFT/IDFT的算法学多项式是一个很有意思的过程。开始的时候你会学习FFT/NTT知道怎么样通过DFT/IDFT快速计算多项式的各种操作。然后你会深入学习多项式的各种运......
  • 多项式全家桶
    还有好一些困难东西没学,现就这样吧。每日一遍:\(167772161,469762049\)除了求逆其他都要预留两倍空间!#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;constllN=(1<<19)+3,H=998244353,g=3,ig=(H+1)/3;intU[N];ull......
  • 多项式模板学习笔记
    多项式乘法存在多项式\(F(z)=\sum_{i=0}^na_iz^i,G(z)=\sum_{i=0}^mb_iz^i\),我们定义多项式乘法:\[F(z)*G(z)=\sum_i\sum_ja_ib_jz^{i+j}\]多项式的点值表达一个\(n\)次函数可以用平面上的\(n+1\)个点来表达。所以我们可以把一个\(n\)次多项式从系数表达转化成\(n+......
  • 多项式乘法(FFT)学习笔记
    Reference:@自为风月马前卒亦@attack的博客这里为了帮助我自己理解,先手推(抄)一遍这位dalao给出的快速傅里叶逆变换的证明。\((y_0,y_1,\dots,y_{n-1})\)为多项式\((a_0,a_1,\dots,a_{n-1})\)在\(x\)取\((\omega^0_n,\omega^1_n,\dots,\omega^{n-1}_n)\)时......
  • 普通有限多项式笔记
    普通多项式笔记\(\textrm{Newton'sMethod}\)(牛顿迭代)应用于解决已知\(g(x)\)的情况下,求出\(g(f(x))\equiv0\modx^n\)。首先通过列出方程显然,\(f(x)\modx^n\)在此时是唯一的。那么我们假设已知\(g(f_0(x))\equiv0\modx^{n/2}\),显然此时\(f_0(x)\modx^{n/2}\)也......
  • P7431【THUPC2017】小 L 的计算题 (牛顿恒等式)(分治NTT)(多项式求逆)题解
    知识点涉及:牛顿恒等式,分治\(NTT\),多项式求逆。这道题有一个推式子之后分治\(NTT+Ln+Exp\)的做法,不过也有一个不用\(Ln+Exp\)的做法(理论常数要小点,实际差不多)。题解:这道题可以牛顿恒等式直接推出一个非常好写的东西。首先看一下牛顿恒等式的描述:对于\(n\)次多项式\(A(......
  • 多项式学习笔记
    1.快速傅里叶变换(FFT)1.1.定义傅里叶变换(法语:TransformationdeFourier,英语:Fouriertransform,缩写:FT)是一种线性变换,通常定义为一种积分变换。其基本思想是一个函数可以用(可数或不可数,可数的情况对应于傅里叶级数)无穷多个周期函数的线性组合来逼近,从而这些组合系数在保有原函......
  • 多项式
    快速傅里叶变换模板题:【模板】多项式乘法(FFT)对于两个多项式\(f,g\),\(f\)的项数为\(n\),\(g\)的项数为\(m\),FFT可以\(O((n+m)\log(n+m))\)地求它们的卷积。多项式点值表示法引理:给定\(n\)个点值\(f(x_0),f(x_1),f(x_2),\dots,f(x_{n-1})\)(\(x_i\)互不相同),可确定唯一......