【洛谷九月月赛T1】签到题（bsgs）（快速乘）

说好的签到题呢qwq。。。。怎么我签到题都不会啊qwq

之后看了bsgs才发现貌似不是那么那么难fake!!什么东西。。。

先贴上部分分做法（也就是枚举1的个数，然后每一步都进行取模（这和最后取模结果一样，但是可以处理更大的整数），判断是否符合题意。这个很好想也很好打，得分70分）：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

long long k,m;

void ans()

{

    long long x=0;

    int cnt=0;

    for(;;)

    {

        cnt++;

        x=(x*10+1)%m;

        if(x==k)

        {

            cout<<cnt<<endl;

            exit(0);

        }

    }

}

int main()

{

    scanf("%lld%lld",&k,&m);

    ans();

    return 0;

}

原题等价于\(10N≡9K+1(modm)10^N\equiv 9K+1\pmod m10N≡9K+1(modm)\)

之后快速乘+BSGS即可

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<map>

using namespace std;

typedef long long ll;

ll k,m;

map<ll,ll> mp;

inline ll mul(ll x,ll y,ll mod)

{

ll tmp=(x*y-(ll)((long double)x/mod*y+1.0e-8)*mod);

return tmp<0?tmp+mod:tmp;

}

//这个是O(1)复杂度的快速乘。。。我在网上抄的，但是我也不太理解是否会出现精度的问题

//但是目前为止貌似是还没有出过锅qwq

//背模板系列（逃）

ll fastpow(ll a,ll x,ll mod){

    ll res=1;

    while(x){

        if(x&1){

            res=mul(res,a,mod);

        }

        x>>=1;

        a=mul(a,a,mod);

    }

    return res;

}

ll BSGS(ll a,ll b,ll p){

    ll m=ceil(sqrt(p));

    ll tmp=b;

    mp.clear();

    for(int i=0;i<=m;i++){

        mp[tmp]=i;

        tmp=mul(tmp,a,p);

    }

    a=fastpow(a,m,p);

    tmp=a;

    for(int i=1;i<=m;i++){

        if(mp.count(tmp))

            return i*m-mp[tmp];

        tmp=mul(tmp,a,p);

    }

    return 0;

}

int main(){

    scanf("%lld%lld",&k,&m);

    k=(k*9+1)%m;

    printf("%lld\n",BSGS(10,k,m));

    return 0;

}