题解 P3846 【 [TJOI2007]可爱的质数】

maohua · 2020-03-11 15:34:24 · 题解

首先，我们回顾一下 Fermat-Oula 定理：m\space|\space a^m-a

把它乘 a 的若干次方：m\space|\space a^{m+k}-a^k

通过 Fermat-Oula 定理，我们可以知道 l \leq p。所以，我们可以用余数的形式来分一下块，把 l 变成 i \times t-j，其中 1 \leq i \leq t,0 \leq j \lt t,t=\lceil \sqrt p \rceil。 那么，我们需要解决的问题变成了：p\space|\space (b^t)^i-n \times b^j

简而言之，b^i \times t 和 n \times b^j 模 p 同余，所以可以直接构造 i 和 j。

那么，如何构造 i 和 j 呢？我们需要分两步：

第一步（Baby Step）：从 0 到 t-1 枚举 j，用一个 map 把 j 映射到 n \times b^j \bmod p里，也就是在 n \times b^j 的余数这个地址存 j。

第二步（Giant Step）：我们通过快速幂可以得到 b^t \bmod p 的值，每次再枚举 i，然后在 map 里找 b^i \times t 为地址中是否有值，若有，则用 i \times t-j 更新答案。

这样，就可以求得最小解了！

代码：

#include<bits/stdc++.h>
using namespace std;
int ans=2147483647;
map<int,int>mp;
void baby_step(int b,int n,int p)
{
  int cs=0,t=sqrt(p-0.5)+1;
  while(cs<t)
  {
    if(!mp[n])mp[n]=cs+1;
    n=1ll*n*b%p,cs++;
  }
}
int powdv(int b,int t,int p)
{
  int ans=1;
  while(t)
  {
    if(t&1)ans=(1ll*ans*b)%p;
    t>>=1;
    b=(1ll*b*b)%p;
  }
  return ans;
}
void giant_step(int b,int n,int p)
{
  int cs=1,t=sqrt(p-0.5)+1,b2;
  b=b2=powdv(b,t,p);
  while(cs<=t)
  {
    if(mp[b])
      ans=min(ans,t*cs-mp[b]+1);
    b=(1ll*b*b2)%p,cs++;
  }
}
int main()
{
  int p,b,n;
  cin>>p>>b>>n;
  baby_step(b,n,p);
  giant_step(b,n,p);
  if(ans<2147483647)cout<<ans<<endl;
  else cout<<"no solution\n";
  return 0;
}

最后推荐我的公众号：这里。