M_sea

洛谷4884 多少个1?
题目描述传送门算法首先,我们可以把n个1写成$\frac{10^n-1}{9}$然后这个式子就变成了然后注意到$m...
扫描右侧二维码阅读全文
19
2018/09

洛谷4884 多少个1?

题目描述

传送门

算法

首先,我们可以把n个1写成$\frac{10^n-1}{9}$

然后这个式子就变成了

$$\frac{10^n-1}{9}\equiv k \pmod m$$

$$10^n-1\equiv 9k \pmod m$$

$$10^n\equiv 9k+1 \pmod m$$

然后注意到$m$是质数,所以可以套上BSGS。

和yyb一起学BSGS

但是$m$最大有$10^{11}$,大概会爆long long。

所以要用龟速乘

但是我常数太大,龟速乘过不去后面两个点。

所以最后选择了__int128,手写输入输出即可。

PS:(其实hash可以用pbds里的gp_hash_table,但是我写的程序无限waiting)

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int __int128
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

inline void write(int x) {
    int sta[30],top=0;
    while (x) sta[++top]=x%10,x/=10;
    while (top) putchar(sta[top--]+'0');
}

inline int FastPow(int a,int k,int p) {
    re int ans=1;
    while (k) {
        if (k&1) (ans*=a)%=p;
        (a*=a)%=p; k>>=1;
    }
    return ans;
}

inline int BSGS(int a,int b,int p) {
    map<int,int> hash; hash.clear();
    b%=p; int t=(int)sqrt((double)p)+1;
    for (re int j=0;j<t;j++) {
        int val=b*FastPow(a,j,p)%p;
        hash[val]=j; 
    }
    a=FastPow(a,t,p);
    if (!a) return (b==0)?1:-1;
    for (re int i=0;i<=t;i++) {
        int val=FastPow(a,i,p);
        int j=hash.find(val)==hash.end()?-1:hash[val];
        if (j>=0&&i*t-j>=0) return i*t-j;
    }
    return -1;
}

mainint main() {
    int k=read(),m=read();
    int ans=BSGS(10,(9*k+1)%m,m);
    write(ans);
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 26 PM

发表评论