题目描述

给定正整数 a,p,b，数据保证 a 和 p 互质。

求满足 ax≡b(modp) 的最小非负整数 x。

输入格式
每个测试文件中最多包含 100 组测试数据。

每组数据中，每行包含 3 个正整数 a,p,b。

当 a=p=b=0 时，表示测试数据读入完全。

输出格式
对于每组数据，输出一行。

如果有 x 满足该要求，输出最小的非负整数 x，否则输出 No Solution。

数据范围

1≤a,p,b≤231−1

样例

输入样例：

3 5 2
3 2 1
0 0 0

输出样例：

3
0

算法1

(分块) $O(np^1/2)$

首先通过欧拉定理a^(phi(p))~1(mod p) =>只需要枚举从0~phi(p)-1,再枚举就phi(p)了,会有a^phi(p)再次同余的结果为1,
开始第二次循环.因此只需要枚举到phi(p)-1就可以了,但是由于p是质数可能会达到接近
int的层次,就会使得phi(p)=p-1过于庞大,这时候就得考虑怎么去优化了,y总的分块思想
就是将[0,p]区间分为长度为k的若干段,而这个k取值为sqrt(p)+1,这样大概可以分为
sqrt(p)块,用k来表示t,于是t=kx-y; 为了遍历从0~p之间的任意一个数 x取到1~k y取到
0~k-1这样把1~p之间的所有数遍历出来,0只需要特判一下就可以了,那么对于一个固定的x,
就可以看是否有一个y使得y代入的余数b * a^y(mod p),是否和a^x(mod p)的余数相同这可以
用hash来实现,先把b * a^y(mod p)所有值放到哈希表里,然后再从小到大枚举x,对于每个x,
判断哈希表里面是否有这个值a^(kx)

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

int bsgs(int a,int b,int p)
{
    if(1%p==b%p)    return 0;

    int k=sqrt(p)+1;//分k块，将[0,p]区间分为长度为k的若干段
    //大概有p^1/2段
    unordered_map<int,int>hash;

    /*
    a^(phi(p))~1(mod p)=>只需要枚举从0~phi(p)-1,再枚举就phi(p)了，开始第二次循环
    但是我们枚举的是0~p,扩大范围
    用k来表示t,于是t=kx-y; 为了遍历从0~p之间的任意一个数 x取到1~k  y取到0~k-1
    这样把1~p之间的所有数遍历出来,0只需要特判一下就可以了,那么对于一个固定的x,
    就可以看是否有一个y使得y代入的余数b*a^y(mod p),是否和a^x(mod p)的余数相同
    这可以用hash来实现,先把b*a^y(mod p)所有值放到哈希表里,然后再从小到大枚举x,
    对于每个x,判断哈希表里面是否有这个值a^(kx)

    a^t=a^(kx-y)~(同余)b(mod p)=>a^kx~a^y*b(mod p)

    */
    for(int i=0,j=b%p;i<k;i++)//这里i是前面说的y
    {
        hash[j]=i;//hash里存的是b*a^y(mod p)-->映射为y
        /*
        括号里有取模
        (1)hash[b*a^0]=0;
        (2)hash[b*a^1]=1;
        (3)hash[b*a^2]=2;
        .......
        */
        j=(ll)j*a%p;//这里j是前面说的b*a^y
    }
    int ak=1;

    for(int i=0;i<k;i++)    ak=(ll)ak*a%p;//求出a^k
    for(int i=1,j=ak;i<=k;i++)//j是前面说的a^(kx)
    {
        if(hash.count(j))    return (ll)i*k-hash[j];//求出t=k*x-y    
        j=(ll)j*ak%p;
    }
    return -1;//不存在这样的t
}

int main()
{
    int a,p,b;
    while(scanf("%d%d%d",&a,&p,&b),a||p||b)
    {
        int res=bsgs(a,b,p);
        if(res==-1) puts("No Solution");
        else cout<<res<<endl;
    }
    return 0;
}