luogu 4884 多少个1？

题目描述:

给定整数K和质数m，求最小的正整数N，使得 11111⋯1（N个1）≡K(mod m)

说人话：就是 111...1111 mod m =K

题解：

将两边一起*9+1，左边就是10^ans，然后BSGS即可。

代码：

#include<map>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

ll k,m;

map<ll,int>mp;

ll fastadd(ll x,ll y,ll p)

{

    ll as1 = x*(y>>)%p*(1ll<<)%p;

    ll as2 = x*(y&((<<)-))%p;

    return (as1+as2)%p;

}

ll fastpow(ll x,ll y,ll p)

{

    ll ret = 1ll;

    while(y)

    {

        if(y&)ret=fastadd(ret,x,p);

        x=fastadd(x,x,p);

        y>>=;

    }

    return ret;

}

ll F2(ll y,ll z,ll p)

{

    ll ret = fastpow(y,p-,p);

    return fastadd(ret,z,p);

}

ll BSGS(ll y,ll z,ll p)

{

    mp[]=;

    ll now = ,m = (ll)sqrt(p);

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

    {

        now=fastadd(now,y,p);

        if(mp.find(now)==mp.end())

        {

            mp[now]=i;

        }

    }

    ll u = ;

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

    {

        ll tmp = F2(u,z,p);

        if(mp.find(tmp)!=mp.end())

        {

            return mp[tmp]+i*m;

        }

        u=fastadd(u,now,p);

    }

}

int main()

{

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

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

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

    return ;

}

巴特西

luogu 4884 多少个1？

最新文章

热门文章