luogu4884 多少个1？

题目链接：https://www.luogu.org/problemnew/show/P4884

套路的将\(111...1\)记做\(\frac{10^n-1}{9}\)，去分母移项的\(10^n\equiv9k+1(mod\ m)\)

直接\(BSGS\)？中间乘会爆long long！

使用龟速乘？这个\(O(log)\)的时间可以让你完美的爆掉

来看一个真正的快速乘（from sxyugao）
\[ a*b=a*(L+R)=a*L+a*R \]
其中\(b=L+R\)，我们让\(L\)取\(b\)的前\(x\)位，\(R\)取\(b\)的后\(x\)位即可

真正的\(O(1)\)快速乘

#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<unordered_map>
using namespace std;
#define int long long
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define fir first
#define sec second
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define maxd 1000000007
#define eps 1e-6
typedef long long ll;
const int N=100000;
const double pi=acos(-1.0);
ll k,m;
unordered_map<ll,int> mp;

int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

ll mul(ll x,ll y,ll p)
{
    if ((x>1e9) || (y>1e9))
    {
        ll l=x*(y>>25ll)%p*(1ll<<25)%p,
           r=x*(y&((1ll<<25)-1))%p;
        return (l+r)%p;
    }
    else return x*y%p;
}
        

ll qpow(ll x,ll y,ll p)
{
    ll ans=1;
    while (y)
    {
        if (y&1) ans=mul(ans,x,p);
        x=mul(x,x,p);
        y>>=1;
    }
    return ans;
}

ll bsgs(ll a,ll b,ll p)
{
    a%=p;b%=p;
    if (!a) return (b==0);
    ll unit=sqrt(p)+1,tmp=b;
    rep(i,0,unit-1)
    {
        mp[tmp]=i;
        tmp=mul(tmp,a,p);
    }
    tmp=qpow(a,unit,p);ll sum=1;
    rep(i,1,unit)
    {
        sum=mul(sum,tmp,p);
        if (mp.count(sum)) return unit*i-mp[sum];
    }
    return -1;
}

signed main()
{
    k=read();m=read();
    printf("%lld",bsgs(10,k*9+1,m));
    return 0;
}

luogu4884 多少个1？

原文：https://www.cnblogs.com/encodetalker/p/10847219.html