一单位元与逆元1单位元不影响运算的元素如加法单位元0乘法1逻辑与1逻辑或0矩阵乘法单位矩阵主对角线左上到右下上所有元素 1 其余位置元素 02逆元一个元素运算它的逆元单位元加法a的逆元是-a a(-a)0乘法a的逆元是a*1不一定所有元素都有逆元二模运算下的加减乘运算与逆元求解1模p的运算体系中的集合是{0123...p-1}可以理解为p,2p,-4p均通过该运算映射到了02加法逆元有所以逆元-a为p-a3乘法逆元暴力枚举范围条件两数成绩模p为1如在mod 9系统中 25互为逆元有费马小定理所以(同余号两边同时乘)所以逆元为所以有快速幂解乘法逆元ll qpow(ll a,ll b,ll mod){ ll ans1; while(b){ if(b1) ansans*a%mod; aa*a%mod; b1; } return ans%mod; }4取余的a-b problema-b取余应为((a-b)%pp)%p解析1有公式如下该式中第一个取余完后出现两种情况一获得负数所以有p后保证其大于等于1二获得正数由于有p干扰其结果所以有第二个%5递推式求逆元先说结论 首先inv[a]有inv[i](p-p/i)*inv[p%i]推导如下显然被除数等于商乘以除数加模数6前缀积求逆元pre[0]1;//pre[]前缀积 for(int i1;in;i) pre[i]pre[i-1]*a[i]%p; invp[n]qpow(pre[n],p-2); for(int in-1;i1;i--) invp[i]invp[i1]*a[i1]%p;//invp[]前缀积的逆元 coutinvp[x]*pre[x-1];//a[x]的逆元7逆元求组合数首先看一下组合数也就是说void init(int n){ fac[0]inv[0]1; for(int i1;in;i) fac[i]fac[i-1]*i%p; inv[n]qpow(fac[n],p-2); for(int in-1;i1;i--) inv[i]inv[i1]*(i1)%p; } ll c(ll n,ll m){ if(nm) return 0; return fac[n]*inv[m]%p*inv[n-m]%p; }三莫比乌斯函数如果x由k个不同的质数相乘得到那么否则为0例如10017*11*13 所以42*2 不是完全不同的 所以四欧拉函数即为求1到n之间与n互质的数的个数若gcd(a,b)1则且五欧拉定理与欧拉筛求逆元如果a,p互质有借此处声明若a,p不互质a无逆元六例题与解析假设约数个数约数之和例题对于正整数 x定义以下 88 个数论函数p(x)表示 x 的最小质因数。特别地规定 p(1)1pnum(x) 表示 p(x) 在 x 的质因数分解中出现的次数即满足 p(x)a∣x的最大非负整数 a。特别地规定 pnum(1)0d(x)表示 x 的正约数个数。μ(x) 表示莫比乌斯函数。规定 μ(1)1如果某个质数的平方整除 x则 μ(x)0否则若 x 含有 k 个不同的质因数则φ(x) 表示欧拉函数即 1 到 x 中与 x 互质的整数个数。sum(x) 表示 x 的所有正约数之和。特别地规定 pp(1)1。。特别地规定 psum(1)1给定正整数 n 和 q 次查询。每次查询给出一个整数 x请输出上述 8 个函数在 x 处的值。代码如下纯板子#includebits/stdc.h using namespace std; #define ll long long const int N1e65; int n,q; int cnt,prime[N],d[N],p[N],pnum[N],mu[N],phi[N],pp[N],psum[N]; ll sum[N]; bool vis[N]; void Euler(int n){ vis[1]mu[1]phi[1]sum[1]d[1]p[1]pp[1]psum[1]1; for(int i2;in;i){ if(!vis[i]){ prime[cnt]i; p[i]i;pnum[i]1;d[i]2;mu[i]-1;phi[i]i-1;pp[i]i;psum[i]i1;sum[i]i1; } for(int j0;jcnti*prime[j]n;j){ vis[i*prime[j]]1; p[i*prime[j]]prime[j]; if(i%prime[j]0){//i与i*prime[j]拥有相同的最小质因数 prime[j] pnum[i*prime[j]]pnum[i]1;//质因子次数比i的多1 d[i*prime[j]]d[i]/(pnum[i]1)*(pnum[i]2); mu[i*prime[j]]0; phi[i*prime[j]]phi[i]*prime[j]; pp[i*prime[j]]pp[i]*prime[j]; psum[i*prime[j]]psum[i]pp[i*prime[j]]; sum[i*prime[j]]sum[i]/psum[i]*psum[i*prime[j]]; break; } //i*prime[j]比i多出了新的最小质因数prime[j] pnum[i*prime[j]]1; d[i*prime[j]]d[i]*2; mu[i*prime[j]]-mu[i]; phi[i*prime[j]]phi[i]*(prime[j]-1); pp[i*prime[j]]prime[j]; psum[i*prime[j]]prime[j]1; sum[i*prime[j]]sum[i]*(prime[j]1); } } } int main(){ scanf(%d%d,n,q); Euler(n); while(q--){ int x; scanf(%d,x); printf(%d %d %d %d %d %lld %d %d\n,p[x],pnum[x],d[x],mu[x],phi[x],sum[x],pp[x],psum[x]); } }借这个题说一下对欧拉筛的理解例题2与素数有关的神秘序列加强版小可获得了一个长度为n的序列1,2,..a1,a2,..an这时他发现假如他按照以下规则再构造一个长度为n的f序列他就能够akioi了。规则如下对于x1或x素数的情况fxx对于x≠1且x≠素数的情况p是x的最小质因子fxfpgcd(x,ax)。当然了对序列f有很多次询问哦。代码如下直接模拟即可重点在欧拉筛#includebits/stdc.h using namespace std; const int N3e65; int a[N],f[N],prime[N],vis[N],cnt; void Euler(int n){ vis[1]f[1]1; for(int i2;in;i){ if(!vis[i]){ prime[cnt]i; f[i]i; } for(int j0;jcnti*prime[j]n;j){ vis[i*prime[j]]1; f[i*prime[j]]f[prime[j]]__gcd(i*prime[j],a[i*prime[j]]); if(i%prime[j]0){//i与i*prime[j]拥有相同的最小质因数 prime[j] break; } //欧拉筛会把所有的合数拆分成i*prime[j] //break保证prime[j]一定是最小质因数或者说所有的合数将被其最小质因数标记vis[i*prime[j]]1 //若j继续则i*prime[j]的最小质因数将不再是prime[j] //举例i18 prime[j]2 此时i*prime[j]36,36被最小质因数2标记合数 //若jprime[j]3 此时i*prime[j]54,54被非最小质因数3标记合数 //后续当i27时54将被重复标记时间复杂度增大 /*即i当可以拆分成prime[j]*x的形式时i%prime[j]0其显然拥有最小质因数prime[j] 若ji*prime[j1]x*prime[j]*prime[j1]显然拥有prime[j]这个更小的质因数却仍被prime[j1]这个更大的质因数标记 */ } } } int main(){ int n; scanf(%d,n); for(int i1;in;i){ scanf(%d,a[i]); } Euler(n); int T,x; scanf(%d,T); while(T--){ scanf(%d,x); printf(%d\n,f[x]); } }今天就这样吧明天还有早休息同学们
