传递性、同乘性、以及一些明了的特性

例题  poj 2417bsgs  http://poj.org/problem?id=2417

BSGS算法

弱鸡的初等数论笔记

整除(小学奥数内容)

  有关性质:
传递性、同乘性、以及一些斐然的质量。

       
还有b|0对于拥有b≠0成立。

       
试着说美素佳儿(Meadjohnson)下:若(a,b)=1,a|n,b|n,则(ab)|n;

 

 

 相关姿势:求出x的持有因子。这些理应都会呢。应该没有更好的复杂度了。

void getd(int x)
{
    for(int i=1;i*i<=x;++i)
        if(x%i==0)
            {
                d[++tot]=i;
                if(i*i!=x)d[++tot]=x/i;
            }
    //sort(d+1,d+tot+1);
}

  

 

 

 

余数和同余(小学奥数内容)

  定义;模意义;

  有关性质:传递性、同加减乘,分化除,以及一些显眼的性能。

       试着证多美滋(Dumex)下:a%p=x,a%q=x,(p,q)=1
  =>   a%(pq)=x;

              尝试用到上面的定律。

  急速幂,龟速乘等等;

  

  中国剩余定理;

  相关难点:

    某校内OJ1272   
 就是板子对吧。

    HDU1788
      思维不要江僵化了。

 

 

 

 

 

 

 

 

有关难点:

  1.codevs1455路径

    一些小拍卖就可以啊。

 

 

 

 

 

 

  2.膜法数字:

    n个数中一定含有1,2,3,4八个数字。求一种排列方式使其膜7为0(鲜明的SPJ)。

    思考一下:新闻学最重大的三种思维是如何?

    那恐怕江会是你们前几日最大的拿走!

 

大胆猜想
不用证明
打表输出

 

 

 

 

 

 

 

 

 

 

 

素数与合数

  定理;1都不是;2是绝无仅有的偶质数。

  筛法:素数的线性筛法。

  分解质因子;spqt(n);

  判定:对于小数,sqrt(n);  

     对于大数,非完美算法
miller-rabin;对于(a,p)=1,有:

         费马小定理:倘若p是质数,那么a^(p-1)≡1(mod
p);

           你会发现那远远不够,比如说561=3*11*17,1105=5*13*17,但无论怎么样它们都… 

         补充定理:假设p是质数,那么a*a≡1(mod
p)的解唯有a=1或p-1。试用初中数学声明。

              开头有点思维推导了。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#include    <ctime>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;
int n;
int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
int Qpow(int d,int z,int mod)
{
  int ans=1;
  for(;z;z>>=1,d=d*d%mod)
    if(z&1)ans=ans*d%mod;
  return ans;
}
bool check(int a,int n,int t,int u)
{
  int x=Qpow(a,u,n);
  while(t--)
    {
      int y=x*x%n;
      if(y==1 && x!=1 && x!=n-1)
    return true;
      x=y;
    }
  return x!=1;
}
// check: return [n must not be a prime];
bool Mr(int n)
{
  if(n==1)return false;
  if(n==2||n==3||n==5||n==7||n==11)return true;
  if(n==4||n==6||n==8||n==9||n==10)return false;
  int m=n-1,j=0;
  while(!(m&1))m>>=1,++j; //n=1+m*2^j
  for(int t=1;t<=10;++t)   //judge 10 times
    {
      int a=rand()%(n-2)+1;
      if(check(a,n,j,m))return false;
    }
  return true;
}
int main()
{
  srand(time(NULL));
  n=gi(),printf("%s\n",Mr(n)?"Yes":"No");
  return 0;    
}

 

 

 

 

 

 

  因数分解;唯一分解定理。

       威尔逊定理。逆定理。

       费马小定理;与欧拉定理之间的关系。(记住欧拉定理就阔以了)。

       因子个数;因子和(其实这些阔以筛出来);

       求大整数因子算法:Fermat;Pollard
Rho;

 

 

 

 

 

 

 

 

 

乘法逆元

  定义;

  性质(用途);证明;

  求法;单个;线性求(必须是质数);

A[i]=-(p/i)*A[p%i];

 

 

 

 

 

  那题你们应当都做过…
…来自于某年升高组;

  NOIP2012 其实并不爱好那种了解就是闭着眼切不精晓就是玩蛋的题

  哦对三行扩大欧几里得代码。领会什么的没要求了。( 反正我是hh 想看的话网上一大堆)

int exgcd(int a,int b,int &x,int &y)
{
    if(!b){x=1;y=0;return a;}
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
int main()
{
    int gcd=exgcd(a,b,x,y);
    // 把  ax+by=gcd(a,b)  的解存储在x,y中。
}    

 

   

  乘法逆元是都要会求的,考点颇多。数论题和组成数学题很多都要用到它。

 

 

 

 

 

 

 

 

GCD与LCM

  定义;

  性质;i*j=gcd(i,j)*lcm(i,j);

  GCD的求法;LCM的求法;

 

 

看起来简单,但实际上…
…下边来做联合思维题

 

 

【题目名:密码  strongbox】 【64MB】 【4s】
【题目描述】
    有一个密码箱,0—n-1中的某些整数是它的密码。
    满足:如果a和b都是它的密码,那么(a+b)%n也是它的密码(a=b是合法情况)。
    欧洲皇帝QT试了k次密码,前k-1次都失败了,最后一次成功了。
    请问:该密码箱最多可能有多少种不同的密码。
【输入格式】
    输入第一行有两个正整数,分别表示n,k。
    第二行为k个非负整数,表示每次试的密码。
    保证存在合法解。
【输出格式】
    一行一个整数,表示结果。
【输入样例1】
    42 5
    28 31 10 38 24
【输出样例1】
    14
【数据规膜】
    对于10%的数据:n≤10^4,k≤100;
    另有10%的数据:n≤10^9,k≤100;
    另有10%的数据:n≤10^9,k=1;
    对于前60%的数据:k≤1000;
    对于100%的数据:1≤k≤250,000≤n≤10^14;

 

 

这道题确实思维难度颇高。我就把解题报告讲(kuai)一讲(kuai)。
首先你得推出2个东西。
1.如果x是密码,那么gcd(x,n)也是密码。
    具体证明联系"扩展欧几里得"知识。
2.如果x,y是密码,那么gcd(x,y)也是密码。
    具体证明同上。

然后我们对密码进行分析。
记尝试密码集合为a;
1.对于密码集合A,里面所有元素的gcd记作X,有X∈A;
    证明:引理2;
2.X是A中最小的元素,且X|gcd(a[k],n);
    证明:引理2,引理1;
3.其他的元素是2X,3X,4X...⌊n/x⌋*x;
    证明:显而易见;
4.X可能有多个解,但多个解不能同时存在。所以X取解集的最小值。
    证明:引理1,答案要求;
5.X与a[j](1≤j<k)互质;
    证明:显而易见;
6.最后的答案就是⌊n/x⌋;

  

 

具体代码实现步骤是什么呢?
1.读入a后,a[k]=gcd(n,a[k]);
2.a[j]=gcd(a[j],a[k]);
    这是为了方便我们节省复杂度。
3.处理出a[k]的所有因子,制造答案可能集;
4.把所有不符合上述结论的因子删掉;
5.找到最小的答案,并输出。

 

具体代码我就不打了,你们想做也做不了,只能嘴巴一下。
为什么呢?
给你一句伤心的话:
Please contact lydsy2012@163.com!

  

 

 

 

 

 

 

 

欧拉函数及欧拉定理

  欧拉函数:定义;

       性质;积性函数;尝试求出图片 1;

 

 

          计算图片 2图片 3

 

       欧拉函数的线性筛(积性);O(sqrt(n))求单个欧拉函数值。

  欧拉定理;

 

 

 

 

 

 

看题。 

 

  引子:求分母小于等于n的最简真分数的个数。

你以为此处会有代码吗
答案就是

图片 4

不要思维江化了啊

 

 

 

 

 

 

 

 

 

 

  1.BZOJ2705 欧拉函数。所以那是答案

 

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;
LL n,Ans;
LL gL()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
LL get(LL x)
{
  LL ans=x;
  for(LL i=2;i*i<=x;++i)
    if(x%i==0)
      {
    ans=ans/i*(i-1);
    while(x%i==0)x/=i;
      }
  if(x!=1)ans=ans/x*(x-1);
  return ans;
}
int main()
{
  n=gL();
  for(LL i=1;i*i<=n;++i)
    if(n%i==0)
      {
    if(i*i==n)Ans+=i*get(i);
    else Ans+=(i*get(n/i)+(n/i)*get(i));
      }
  printf("%lld\n",Ans);
  return 0;
}

由此有的省的省选如故有很水的题的,不像某南。

 

 

 

 

 

 

 

 

  2.
BZOJ2818
 BZOJ2190 所以那两题很水咯。

 

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
#define Inc i*Prime[j]
using namespace std;
const int N = 10010000;
int n,Prime[N],tot,ph[N],vis[N];
LL Q[N],Ans;
int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
LL gl()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
void prepare()
{
  ph[1]=1;
  for(int i=2;i<=n;++i)
    {
      if(!vis[i]){Prime[++tot]=i;ph[i]=i-1;}
      for(int j=1;j<=tot;++j)
    {
      if(Inc>N)break;vis[Inc]=1;
      if(i%Prime[j])ph[Inc]=ph[i]*ph[Prime[j]];
      else{ph[Inc]=ph[i]*Prime[j];break;}
    }
    }
  for(int i=2;i<=n;++i)
    Q[i]=Q[i-1]+(LL)ph[i];
}
int main()
{
  n=gi();prepare();
  for(int i=1;i<=tot;++i)
    Ans+=(2*(Q[n/Prime[i]])+1);
  printf("%lld",Ans);
  return 0;
}

 

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
#define Inc i*Prime[j]
using namespace std;
const int N = 40100;
int n,vis[N],Prime[N],ph[N],tot,Ans;
int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
void pui(int x)
{
  if(x<10)putchar(x+'0');
  else pui(x/10),putchar(x%10+'0');
}
void shai()
{
  ph[1]=1;
  for(int i=2;i<=n;++i)
    {
      if(!vis[i]){Prime[++tot]=i;ph[i]=i-1;}
      for(int j=1;j<=tot;++j)
        {
          if(Inc>n)break;vis[Inc]=1;
          if(i%Prime[j])ph[Inc]=ph[i]*ph[Prime[j]];
          else {ph[Inc]=ph[i]*Prime[j];break;}
        }
      Ans+=ph[i];
    }Ans-=ph[n]-1;
}     
int main()
{
  n=gi();shai();
  printf("%d",Ans*2+1);
  return 0;
}

 

 

 

 

 

 

 

 

   

 

 

 

 

 

  3.
BZOJ1951 考的可比多,板子合集,还带了某些构思,是道不错的题。  

 

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;
const LL Mod = 999911659;
const int N = 50010;
LL n,g,M[]={0,2ll,3ll,4679ll,35617ll},Y[10];
LL J[N],A[N],Z[10];
void pL(LL x)
{
  if(x<10)putchar(x+'0');
  else pL(x/10),putchar(x%10+'0');
}
LL gL()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
void prepare(LL x)
{
  A[1]=J[0]=J[1]=1;
  for(LL i=2;i<x;++i)
    J[i]=J[i-1]*i%x,A[i]=((-(x/i)*A[x%i])%x+x)%x;
}
LL C(LL N,LL M,LL P)
{
  if(N<M)return 0ll;
  LL ans=J[N];
  ans*=A[J[M]];ans%=P;
  ans*=A[J[N-M]];ans%=P;
  return ans;
}
LL Lucas(LL N,LL M,LL P)
{
  if(!M)return 1ll;
  if(N<P&&M<P)return C(N,M,P);
  LL c=C(N%P,M%P,P);if(!c)return 0ll;
  LL L=Lucas(N/P,M/P,P);return c*L%P;
}
LL get(LL mod)
{
  LL ans=0;
  for(LL i=1;i*i<=n;++i)
    if(n%i==0)
      {
      ans+=Lucas(n,i,mod);ans%=mod;
      if(i*i!=n)ans+=Lucas(n,n/i,mod),ans%=mod;
      }
  return ans;
}
LL Qpow(LL d,LL z)
{
  LL ans=1;
  for(;z;z>>=1,d=d*d%Mod)if(z&1)ans=ans*d%Mod;
  return ans;
}
int main()
{
  n=gL();g=gL()%Mod;
  if(g==0){pL(0);return 0;}
  for(int t=1;t<=4;++t)
    {
      prepare(M[t]);
      Y[t]=get(M[t]);
      Z[t]=((Mod-1)/M[t])*A[((Mod-1)/M[t])%M[t]];
      Y[0]+=Y[t]*Z[t]%(Mod-1);Y[0]%=(Mod-1);
    }
  return pL(Qpow(g,Y[0])),0;
}

 

 

 

 

 

 

  4. BZOJ1408 提示:积性,结合率,递×。

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
#define ls (x << 1)
#define rs (x << 1 | 1)
using namespace std;
const LL Mod = 10000;
LL F[1010][1010],Ans1,Ans2,m,k;
int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
void pL(LL x)
{
  if(x<0)putchar('-'),pL(-x);
  if(x<10)putchar(x+'0');
  else pL(x/10),putchar(x%10+'0');
}
void pc(){putchar('\n');}
LL gL()
{
  LL x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
LL Qpow(LL d,LL z)
{
  LL ans=1;
  for(;z;z>>=1,d=d*d%Mod)if(z&1)ans=ans*d%Mod;
  return ans;
}
int main()
{
  k=gL();m=1;
  for(LL i=1;i<=k;++i)
    {
      LL p=gL(),e=gL();
      m=m*Qpow(p,e)%Mod;
      if(p==2)continue;
      LL ans1=(Ans1+(Ans2+1)*(p-1))%Mod;
      LL ans2=(Ans2+Ans1*(p-1))%Mod;
      Ans1=ans1;Ans2=ans2;
    }
  pL(Ans2);pc();pL(Ans1);pc();pL(((m-Ans1-Ans2-1)%Mod+Mod)%Mod);
  return 0;
}

 

  

 

 

 

 

 

 

 

 

 

 

 

  最终来道水题放放松。李电出过的题,大家应该都切过。

   BZOJ3884

#include    <iostream>
#include    <cstdio>
#include    <cstdlib>
#include    <algorithm>
#include    <vector>
#include    <cstring>
#include    <queue>
#define LL long long int
using namespace std;
int n,p;
int gi()
{
  int x=0,res=1;char ch=getchar();
  while(ch>'9'||ch<'0'){if(ch=='-')res*=-1;ch=getchar();}
  while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
  return x*res;
}
void pL(int x)
{
  if(x<0)putchar('-'),pL(-x);
  if(x<10)putchar(x+'0');
  else pL(x/10),putchar(x%10+'0');
}
int Qpow(int d,int z,int Mod)
{
  int ans=1;
  for(;z;z>>=1,d=(LL)d*d%Mod)if(z&1)ans=(LL)ans*d%Mod;
  return ans;
}
int phi(int x)
{
  int Txd=x;
  for(int i=2;i*i<=x;++i)
    if(x%i==0)
      {
        Txd-=Txd/i;
        while(x%i==0)x/=i;
      }
  if(x>1)Txd-=Txd/x;
  return Txd;
}   
int f(int p)
{
  if(p==1)return 0;int x=phi(p);
  return Qpow(2,x+f(x),p);
}
int main()
{
  int T=gi();
  while(T--)pL(f(gi())),putchar('\n');
  return 0;
}

 

 

 

 

 

 

 

 

 

     

原根与离散对数

  先来探望那道题怎么写。

  某校内OJ 1508。求 a^x≡1 (mod
b)。

  当时自我做那题时还太naive,现在考虑很简短是吧?

  介绍一下原根和离散对数。(你们随便听听就够了,有点超)

  原根:

    对于2个互质的数a,b,由欧拉定理知,必定存在x≤φ(b),使a^x≡1
(mod b);

    x记作a对模m的阶,记作δm(a);(应该是长那么些呢)

1^1≡1(modn),1对模n的阶为1;
2^2≡1(mod3),2对模3的阶为2;
5^6≡1(mod7),5对模7的阶为6;
2^3≡1(mod7),2对模7的阶为3;

 

    由此,定义Ordm(a)为驱动a^x≡1
(mod m) 的小小整数解x;

    如果有Ordma=φ(m),则称a是模m的一个原根。**

    我了然刚刚看完的终将一脸蒙蔽…
…我也是。

  原根的关于性质,我蒯了一些。

    (1).具有原根的数一定是:2,4,p^n,2(p^n),其中p为奇素数。

    (2).m的纤维原根大小是O(m0.25)的。所以有些东西你枚举就够了(惨疼的教训)。

**    (3).借使模m有原根,那么它有φ(φ(m))个原根。(防止有人出结论题)。**

**  求原根的主意:**

你们不是已经知道了吗?

 

 

离散对数

  初等代数中的对数运算,定义即便有ax=b,则称x是以a为底的对数,记作logab;

  在同余关系中也有相近的题材。给定n,a,b,如何求解x使ax≡b
(mod n);

  这一标题也被称作离散对数难点。大家只谈谈n为素数的情状。

  先来商讨暴力如何是好?

  由欧拉定理,大家知道0~n-1内必有一解,递推即可,复杂度O(n);

  但这么并不是很好的算法,上边给出一种O(比n小)的算法。

 

 

 

 

 

首先计算出x=0,1,2…m时ax
(mod n)的值。

设ak≡b (mod n);设
k=p*m+q(q<m);枚举p;

对于一个枚举出的p,ap*m是一定且可求的。

则足以改写成: ap\*m+qb (mod n);

   继续改: aq*apm≡b (mod n);**

*   再一步: aq\(am)pb (mod n);**

   设T=(am)p,就有:

*        T\aqb (mod n);**

   你就足以用exgcd求出T;

   那么难点就在于求q上。聪明的你能够用很七种办法解决那几个难题。。。

   那种分块用基本不等式算出m取到sqrt(n)时复杂度最精良。。。

 

 

 

 

练习题:

  BZOJ2956 模积和;

  BZOJ1407 Savage(NOI 2002
荒岛野人);

  NOIP2014 Day2T3 解方程,同BZOJ2742
Akai的数学作业;

  神题之圆上的整点;

  神题之数论之神CJK;

  其实上面的标题自己一个都不会。

那是一道bsgs标题,用bsgs算法,又称大小步(baby step giant
step)算法,或者拔(b)山(s)盖(g)世(s)算法,或者北(b)上(s)广(g)深(s)算法。。。

给定y、z、p,总括满足yx mod
p=z的矮小非负整数x。p为质数(没办法写数学公式,以下内容用心去感受呢)

难点大意就是

x = i*m + j.

给定a,b,p,求最小的非负整数x,满足  ax ≡ b(mod p)

y^(j)≡z∗y^(-i*m)) (mod p)

 

y^(j)≡z∗ine(y^(i*m)) (mod p)(逆元)

先令 x = i*m-j,其中 m=ceil(sqrt(p)),ceil是进化取整。

由费马小定理y^(p-1)≡1 (mod p)ine(y^m) = y^(p-m-1) 

这么原式就成为     ai\*m-j = b (mod p),

ine(y^(i*m)≡ine(y^((i−1)m))∗y^(p-m-1) 

移项就变成了        ai\*m = b*aj (mod p)

1.首先枚举同余符号左面,用一个hash保存(y^j,j),因为j可能等于0,所以hash[1]要赋为一个特有值。

枚举j (范围0-m) ,将 b*aj\  存入hash表。

2.再枚举同余符号右面,假如hash(**z∗ine(y^(i*m)))**存在,就找到了一组解。

枚举i (范围1-m) ,从hash表中寻找第三个满足ai\*m =
b*aj\  (mod p)。

精晓,m=sqrt(p)的时候复杂度最低为O(sqrt(p)),m=ceil(sqrt(p)).

此时   x = i*m-j  就是所须要的。

 

 

从此人博客中得以见见,此人对此BSGS算法有着万分深厚的接头,居然可以找到俩个牵动学习BSGS算法的俩首歌,还用了exgcd算法。

那么为何只总计到 m=ceil(sqrt(q))  就足以确定答案吧?

http://www.cnblogs.com/yuiffy/p/3877381.html

因为 x = i*m-j , 所以x 的最大值不会当先p

 

a(k\ mod\ p-1) = ak (mod p)
 申明那几个公式,(须求用到费马小定理)

其余俩个操作为连忙幂,exgcd。

k mod p-1 就是 k-m(p-1) ,原式就改为了 ak-m(p-1) ≡ ak (mod p)

因为难题并不是一道写的,所以写了俩个高速幂。

再变一步  a/ am(p-1) ≡ ak
(mod
p)

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<cmath>
using namespace std;

int T,k;
long long y,z,p;
map<int,int> hash;

long long q(long long z) {
    if(z==1) return y%p;
    long long m=q(z/2);
    if(z%2) return (((m*m)%p)*y)%p;
    return (m*m)%p;
}

void solve1() {
    printf("%lld\n",q(z));    
}

long long exgcd(long long a,long long b,long long &x,long long &y) {
    if(b==0) {
        x=1; y=0;
        return a;
    }
    long long res=exgcd(b,a%b,y,x);
    y-=(a/b)*x;    
    return res;
}

void solve2(long long a,long long b,long long n) {
    long long x,y,ans,d,s;
    d=exgcd(a,n,x,y);
    if(b%d!=0) printf("Orz, I cannot find x!\n");
    else {
        ans=(b/d)*x; s=n/d;
        ans=(ans%s+s)%s;
        printf("%lld\n",ans);
    }
}

long long power(long long a,long long b,long long mod) {
    long long res=1;
    while(b) {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

void solve3() {
    y%=p; z%=p;
    if(!y && !z) printf("1\n");
    else if(!y) printf("Orz, I cannot find x!\n"); 
    else {
        long long m,v,e,res;
        m=ceil(sqrt(p)); v=power(y,p-m-1,p); e=1;    

        hash.clear();
        hash[1]=m+1;
        for(long long i=1;i<=m;i++) {
            e=e*y%p;
            if(!hash[e]) hash[e]=i;    
        }

        res=-1;
        for(long long i=0;i<m;i++) {
            if(hash[z]) {
                res=i*m+(hash[z]==m+1?0:hash[z]);
                break;            
            }
            z=z*v%p;            
        }
        if(res==-1) printf("Orz, I cannot find x!\n");
        else printf("%d\n",res);
    }
}

int main() {
    scanf("%d%d",&T,&k);
    while(T--) {
        scanf("%lld%lld%lld",&y,&z,&p);
        if(k==1) solve1();
        else if(k==2) solve2(y,z,p);
        else solve3();
    }
    return 0;
}

这时让 am(p-1) ≡ 1 (mod p)
就行了。

由费马小定理知: 当p为质数且 (a,p) = 1 时 ap-1
≡ 1 (mod p)

从而推出 p 为质数 且 (a,p)=1 那一个规则,
所以 a(k\ mod\ p-1) ≡ a (mod p) 

之所以:假设枚举 x 的话枚举到 p 即可。

就此使 im−j<=p
, 即 m=⌈√p⌉
, i,j 最大值也为m。

 

 那是代码,结合方面的看

图片 5图片 6

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<map>
 4 #include<cmath>
 5 
 6 using namespace std;
 7 typedef long long ll;
 8 
 9 map<ll,int>mp;
10 ll p,a,b;
11 ll n,m,now,ans,t;
12 bool flag;
13 
14 ll fast_pow(ll x)
15 {
16     ll sum = 1;
17     ll aa = a;
18     while (x>0)
19     {
20         if (x&1) 
21             sum = (sum*aa)%p;
22         x = x>>1;
23         aa = (aa*aa)%p;
24     }
25     return sum;
26 }
27 int main()
28 {
29     while(scanf("%lld%lld%lld",&p,&a,&b)!=EOF)
30     {
31         if(a%p==0)
32         {
33             printf("no solution\n");
34             continue;
35         }
36         mp.clear();
37         m = ceil(sqrt(p));
38         flag = false ;
39         now = b%p;        //b*a^j 当j==0时 
40         mp[now] = 0;
41         for(int i=1;i<=m;++i)
42         {
43             now = (now*a)%p;
44             mp[now] = i;
45         }
46         t = fast_pow(m);
47         now = 1;
48         for(int i=1;i<=m;++i)    //枚举 (a^m)^i
49         {
50             now = (now*t)%p;
51             if(mp[now])
52             {
53                 flag = true;
54                 ans = i*m-mp[now];
55                 printf("%lld\n",(ans%p+p)%p);    //printf("%lld\n",(ans%p+p)%p);
56                 break;
57             }
58         }
59         if(!flag) printf("no solution\n");
60     }
61     return 0;
62 }

bsgs

 

相关文章