[BZOJ2219] 数论之神

摘要

啃课件的时侯遇到的,先放个题解,至于代码的话先咕着

多组数据(<1000)对于给定的 3 个非负整数 a,b,k 求出满足> 1. .

  1. X 在范围 [0, 2K] 内

的 X 的个数.

即求同余方程 的解的个数。 . 则原方程的解即为 的解的乘积(根据中国剩余定理)

问题变成求

的解的个数. 分类讨论如下

Case1

如果 ,即 b 是 的倍数,则原方程为 .

显然 x 只可能是 p 的倍数,那么设 ,则要求 .

于是求得 . 则 x 的最小值为 ,显然解的数量就是剩余系中 的倍数,即 .

Case2

2019.6.12 来填坑啦

如果 ,即两者互质。

由于素数的幂一定有原根,因此可以将方程转化为离散对数方程。假设 的一个原根是 r。

。那么可以利用 BSGS 求解 B,由于离散对数与原数一一对应,即 X 与 x 是一一对应的。因此原方程解的个数就等于离散对数方程的解的个数。

根据扩欧推论,若 ,那么方程有解,解的数量就是 (a,P);否则无解。

Case3

如果 .

则可以记 . 方程变为

显然,如果 ,那么方程无解。根据同余方程的一些性质变化如下

由于 (p,q)=1,这就转化为了 Case2.

这样求完后,注意到 ,因此 . 但是上述方程中, 。因此最后要把求出的值乘上 .


  转载请注明: Sshwy's Blog [BZOJ2219] 数论之神

 上一篇
原根与模算术 原根与模算术
摘要 啃课件的时侯遇到的数论题,于是来填坑 阶与原根如果 (a,m)=1,记 x 为最小的正整数使得 . 那么 x 称为 的阶。记为 。 可以把阶理解为模意
2019.06.08
下一篇 
[Luogu2022] 有趣的数 [Luogu2022] 有趣的数
摘要 题意:Q(N,K) 表示把 1-N 按字典序从小到大排列后 K 的排名。给出 K,M,最小化 N,且 Q(N,K)=M. 无解输出 0。 一道思路很清奇的题。首先可以想到这些结论: 关于 i 单调递增(非严格)
2019.06.08
  目录