Codeforces Round #460 (Div. 2) E. Congruence Equation （CRT+数论）

题目链接：

http://codeforces.com/problemset/problem/919/E

题意：

让你求满足 $na^n\equiv b \pmod p$ 的 $n$ 的个数。

$2 ≤ p ≤ 10^{6} + 3, 1 ≤ a, b < p, 1 ≤ x ≤ 10^{12}$.

题解：

因为：

$n \mod p $的循环节是 $p$

$a^{n} \mod p$的循环节是 $p-1$。(费马小定理)

所以： $na^n \mod p$的循环节为 $p*(p-1)$。

因为 $p$是质数。

假设: $n \mod p \equiv i, a^n\mod p\equiv a^j$.

$a^n \mod p \equiv i$ ----①

$a^n\mod p\equiv a^j $ ----②

$na^n\equiv b \pmod p$ ----③

可以得到： $i \times a^j \equiv b \pmod p$.

我们现在枚举的$a^n$ 中的 $n$ 为 $j$ , 满足 $n \times a^n\ mod\ p\ = \ b$ 的 $n$ 为 $i$.

列出同余方程：

$i \equiv b*a^{-j} \pmod p $ ---①

$i\equiv j \pmod {p-1}$ ---②

利用 $CRT$ 可以解出：$i=(p-1)^2ba^{-j}+pj$ ，其中 $a^{-j}$ 是$ a^{j}$ 在 $\mod p $意义下的逆元。

因为在所有 $<=x$ 的 $i$ 的倍数都满足条件，除法统计一下即可。

复杂度：$O(p*logp)$

代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll qpower(ll a,ll b, ll mod)

{

  ll ans = 1;

  while(b){

    if(b&1) ans = ans * a % mod;

    b>>=1;

    a=a*a%mod;

  }

  return ans;

}

ll a,b,mod,x;

int main(int argc, char const *argv[]) {

  std::cin >> a >> b >> mod >> x;

  ll ans = 0;

  for(int i = 1;i <= mod-1;i++) {

    ll  c = qpower( qpower(a, i , mod) , mod - 2, mod) * b % mod;

    ll  n = ((mod-1) * (mod-1) * c + mod * i) % (mod * (mod-1));

    ans += ( x / (mod * (mod-1)) ) + (x % (mod * (mod-1)) >= n );

  }

  std::cout << ans << '\n';

  return 0;

}

巴特西

Codeforces Round #460 (Div. 2) E. Congruence Equation （CRT+数论）

题目链接：

http://codeforces.com/problemset/problem/919/E

题意：

让你求满足 \(na^n\equiv b \pmod p\) 的 \(n\) 的个数。

\(2 ≤ p ≤ 10^{6} + 3, 1 ≤ a, b < p, 1 ≤ x ≤ 10^{12}\).

题解：

因为：

$n \mod p $的循环节是 \(p\)

\(a^{n} \mod p\)的循环节是 \(p-1\)。(费马小定理)

所以： \(na^n \mod p\)的循环节为 \(p*(p-1)\)。

因为 \(p\)是质数。

假设: \(n \mod p \equiv i, a^n\mod p\equiv a^j\).

\(a^n \mod p \equiv i\) ----①

$a^n\mod p\equiv a^j $ ----②

\(na^n\equiv b \pmod p\) ----③

可以得到： \(i \times a^j \equiv b \pmod p\).

我们现在枚举的\(a^n\) 中的 \(n\) 为 \(j\) , 满足 \(n \times a^n\ mod\ p\ = \ b\) 的 \(n\) 为 \(i\).

列出同余方程：

$i \equiv b*a^{-j} \pmod p $ ---①

\(i\equiv j \pmod {p-1}\) ---②

利用 \(CRT\) 可以解出：\(i=(p-1)^2ba^{-j}+pj\) ，其中 \(a^{-j}\) 是$ a^{j}$ 在 $\mod p $意义下的逆元。

因为在所有 \(<=x\) 的 \(i\) 的倍数都满足条件，除法统计一下即可。

复杂度：\(O(p*logp)\)

代码：

最新文章

热门文章

巴特西

Codeforces Round #460 (Div. 2) E. Congruence Equation （CRT+数论）

题目链接：

http://codeforces.com/problemset/problem/919/E

题意：

让你求满足 \(na^n\equiv b \pmod p\) 的 \(n\) 的个数。

\(2 ≤ p ≤ 10^{6} + 3, 1 ≤ a, b < p, 1 ≤ x ≤ 10^{12}\).

题解：

因为：

$n \mod p $的循环节是 \(p\)

\(a^{n} \mod p\)的循环节是 \(p-1\)。(费马小定理)

所以： \(na^n \mod p​\)的循环节为 \(p*(p-1)\)。

因为 \(p\)是质数。

假设: \(n \mod p \equiv i, a^n\mod p\equiv a^j\).

\(a^n \mod p \equiv i\) ----①

$a^n\mod p\equiv a^j $ ----②

\(na^n\equiv b \pmod p\) ----③

可以得到： \(i \times a^j \equiv b \pmod p\).

我们现在枚举的\(a^n\) 中的 \(n\) 为 \(j\) , 满足 \(n \times a^n\ mod\ p\ = \ b\) 的 \(n\) 为 \(i\).

列出同余方程：

$i \equiv b*a^{-j} \pmod p $ ---①

\(i\equiv j \pmod {p-1}\) ---②

利用 \(CRT\) 可以解出 ：\(i=(p-1)^2ba^{-j}+pj\) ，其中 \(a^{-j}\) 是$ a^{j}$ 在 $\mod p $意义下的逆元。

因为在所有 \(<=x\) 的 \(i\) 的倍数都满足条件，除法统计一下即可。

复杂度：\(O(p*logp)\)

代码：

最新文章

热门文章

所以： \(na^n \mod p\)的循环节为 \(p*(p-1)\)。

利用 \(CRT\) 可以解出：\(i=(p-1)^2ba^{-j}+pj\) ，其中 \(a^{-j}\) 是$ a^{j}$ 在 $\mod p $意义下的逆元。