原根(半转载)

原根定义:

设m是正整数,a是整数,若a模m的阶等于φ(m),则称a为模m的一个原根。(其中φ(m)表示m的欧拉函数)(from 51nod)

原根要求

k有原根当且仅当k=2,4,pa,2pak=2,4,p^a,2p^a 其中p是奇素数,a是正整数

如何找模k的最小原根:

暴力枚举判断是不是满足条件。

判断算法:

(首先保证gcd(a,m)=1\gcd(a,m)=1

暴力

假设要判断的数为s,判断2到ϕ(k)1\phi(k)-1中是否有一个正整数t满足 ,如果有则不是,否则就是。 时间复杂度O(ϕ(k))O(\phi(k)),其实就是O(k)O(k)

更快速的方法

x=ϕ(k)x=\phi(k),对于每个x的素因数p判断 是否为1。如果是则s不是原根。如果都不是则s是原根。

感性理解吧。

最长回文子串--Manacher算法

概述

对于求最长回文子串的暴力算法,一般是枚举对称轴然后不断扩展,时间复杂度O(n2)O(n^2)。 暴力算法有两点缺点:

  1. 对称轴可能是一个字母也可能是两个字母之间,需要两次枚举。
  2. 扩展可能会出现多余的重复。

CF55D

传送门

简要题意

定义一个正整数为美丽的当且仅当这个数能被所有非零位上的数整除。 给定ll,rr,求llrr中有多少数是美丽的。 多组数据,l,r9×1018l,r\le 9\times 10^{18}

约瑟夫问题的一些解法

约瑟夫问题:

有n个人,编号为1..n1..n,从第1个人开始报数,报到m的人离开,求最后的幸存者。

算法1(Simple算法):

用队列模拟,可以算出每一次出队的人。

时间复杂度O(nm)O(nm)

当n很小而m很大时,可以通过取膜将O(nm)O(nm)优化为O(n2)O(n^2)

UOJ164 V

传送门

题意:维护一个数列a1...ana_1...a_n,有以下5种操作:

  1. al..ar=al..ar+xa_l..a_r=a_l..a_r +x
  2. al..ar=max(al..arx,0)a_l..a_r=max(a_l..a_r-x,0)
  3. al..ar=xa_l..a_r=x
  4. 查询axa_x
  5. 查询axa_x历史最大值

ARC082C ConvexScore

简要题意

给定n个点,定义一个凸多边形包含点数s为:这个凸多边形覆盖的点数-这个凸多边形的角数(每一个角 )

设总点集为A。 这个凸多边形的分值为为:2s2^s

求由这n个点构成的所有凸多边形的分值和mod998244353mod 998244353

|

博客使用Disqus作为评论系统