解题报告：luogu P4884

题目链接：P4884 多少个1？
如此\(zz\)的紫题实属少见，难度在于\(BSGS\)板子吧。
啊？如此强的您不会\(BSGS\)，那一定在fake,没事，全套准备好了：\(Link\)
对于这道题，考虑推式子：
显然题目让我们求的是满足：

的\(n\)的最小值。
发现有等比数列求和的模型，可以搞一下，去掉求和式：

\(emmm......\)，很简单了：

可以暴力\(BSGS\)了，复杂度是\(O(\sqrt{m}\log m)\)，可以通过本题，不过好像需要用快速乘（我有一个好想法......

\(Code\):

\(ps\):等下，我先不发代码，因为尛了同校巨佬，为了防止报真名，这里就删去了\(qwq\)，关于怎样优雅地\(orz\)，我会在不久随便写写的，（大佬保佑\(AC\)，真好
下面是代码了:

#include<iostream>
#include<cstdio>
#include<algorithm> 
#include<cmath>
using namespace std;
//不和谐因素被和谐了
#define ll long long
ll k,m;
#define read(x) scanf("%lld",&x) 
#define MAXN 500005
inline long long mul(long long x,long long y,long long mod)
{
	long long tmp=(x*y-(long long)((long double)x/mod*y+1.0e-8)*mod);
	return tmp<0 ? tmp+mod : tmp;
}
struct node
{
	ll id,val;
}b[MAXN];
bool cmp(node n,node m){if(n.val^m.val) return n.val<m.val;else return n.id>m.id;}
void make(ll mod,ll x,ll n,ll y)
{
	ll now=x%mod;
	for(int i=0;i<n;i++)
	{
		b[i+1].val=now,b[i+1].id=i;
		now=mul(now,y,mod)%mod;
	}
	sort(b+1,b+n+1,cmp);
	return;
}
ll quickpow(ll a,ll b,ll mod)
{
	ll ans=1,base=a;
	while(b)
	{
		if(b&1) ans=mul(ans,base,mod)%mod;
		b>>=1;
		base=mul(base,base,mod)%mod; 
	}
	return ans%mod;
}
ll find(ll mod,ll a,ll n)
{
	ll rt,kel;
	rt=kel=quickpow(a,n,mod);
	for(int i=1;i<=n;i++)
	{
		int l=1,r=n,mid;
		while(l<=r)
		{
			mid=(l+r)>>1;
			if(l==r) break;
			if(b[mid].val<rt) l=mid+1;
			else r=mid;
		}
		if(b[mid].val==rt) return 1ll*n*i-(ll)b[mid].id;
		rt=mul(rt,kel,mod)%mod;
	}
}
ll BSGS(ll x,ll y,ll p)
{
	ll h=ceil(sqrt(p));
	make(p,y,h,x);
	return find(p,x,h);
}
int main()
{
	read(k),read(m);
	printf("%lld\n",BSGS(10,(9*k+1)%m,m));
	return 0; 
}

解题报告：luogu P4884

原文：https://www.cnblogs.com/tlx-blog/p/12594355.html