zcmimi's blog

arrow_back原根共3篇文章

avatar
zcmimi
2020-07-05 15:56:00

阶:

定义:

m>1\gcd(a,m)=1,那么使得a^r \equiv 1 \pmod m成立的最小的正整数r称为a对模m的阶,记为\delta_m(a),或ord_m a

定理:

  1. m>1gcd(a,m)=1,满足$a^n\
avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

https://zoj.pintia.cn/problem-sets/91827364500/problems/91827370149

题意:

给一个序列A,要求支持以下操作:

  1. 区间乘

  2. 区间里所有数都变成自己的k次幂

  3. 求区间乘积(mod 10000000007)

由于模数是质数,所以可以将每个数都变成原根的次幂

这样区间乘转化为区间加,区间次幂转化为区间乘,求区间乘积转化为求区间和

avatar
zc
2020-07-07 17:25:00
查看原题

点击跳转

首先了解原根

这里利用到原根的一个性质:

gm的一个原根
g^0,g^1,g^2,\dots,g^{\varphi(m)-1}构成模m的简化剩余系

这样我们可以把序列中所有数变成原根的次幂,

那么序列中所有数的乘积就可以转化为他们的和

设这个和为sum

设生成函数:\displaystyle f(x)=\sum_{i=0}^m [i\in S]x^i

可以发现f(x)^n次数为sum的那一项的系数就是答案

使用快速幂+快速数论变换

1/1
Search
search