luogu P4884 多少个1？

LINK：多少个1？

题目要求：\(\sum_{i=0}^{n-1}10^i \equiv k \mod m\) 最小的n。

看起来很难求的样子这个同余式看起来只能暴力枚举。

不过既然是同余我们等式两边就可以同时进行加减乘运算。

考虑转换成我们熟悉的模型而这个形式比较像高次同余方程。

等式两边同乘 9 再加一等式变成 \(10^n\equiv 9*k+1\mod m\)

显然这是一个高次同余方程我们直接BSGS即可。

但是m和10显然有可能是不互质的所以我们需要一个扩展BSGS (扩展拔山盖世算法。

哦 m保证为质数那打扰了。。

但是模数有可能m>int 所以我们需要龟速乘这样的话复杂度就是log^2的了且log是跑满的。所以非常的慢。

const ll MAXN=100010;

ll mod,n;

map<ll,ll>H;

inline ll gsc(ll a,ll b)

{

	ll cnt=0;

	while(b)

	{

		if(b&1)cnt=(cnt+a)%mod;

		b=b>>1;a=(a+a)%mod;

	}

	return cnt;

}

inline ll BSGS()//求 10^x%mod=n; x>1

{

	ll w=(ll)sqrt(mod*1.0)+1;

	ll ww=1;

	rep(1,w,i)

	{

		ww=ww*10%mod;

		ll cc=gsc(ww,n)%mod;

		H[cc]=max(H[cc],i);

	}

	ll cc=ww;

	rep(1,w,i)

	{

		if(H.find(cc)!=H.end())return i*w-H[cc];

		if(cc==n)return i*w;

		cc=gsc(cc,ww)%mod;

	}

	return 114514;

}

int main()

{

	freopen("1.in","r",stdin);

	get(n);get(mod);

	n=n*9+1%mod;

	putl(BSGS());

	return 0;

}

其实完全不需要快速幂我们颠倒一下两部分先求出右部分即可。

当然也可以快速幂了那个时候不过不能再龟速乘了。

考虑一种较快的乘法：

比较常见的是转long double 的快速乘。

long double精度不够的时候会丢弃后面的位。

考虑 a%p=a-(a/p)p; 那么 ab%p=ab-(ab/p)*p;

如果p过大的时候我们会丢掉 a*b后面的一些位但是这些位同时也产生不了贡献

所以这样做是可行的。具体的我再思考一下。

inline LL ksc(LL a,LL b,LL p)//long double版本的快速乘

{

    a%=p;b%=p;

    long long c=(long double)a*b/p;

    long long ans=a*b-c*p;

    if(ans<0) ans+=p;

    else if(ans>=p) ans-=p;

    return ans;

}

巴特西

luogu P4884 多少个1？

最新文章

热门文章