2019牛客暑期多校训练营（第三场）D.Big Integer(费马小定理+找循环节)

题意

已知序列$A$A为$1,11,111,1111,...$1,11,111,1111,...，求
$\sum_{i=1}^n\sum_{j=1}^m[A(i^j)\%p==0]$i=1∑n​j=1∑m​[A(ij)%p==0]

思路

易知$A(n)=\frac{10^n-1}{9}$A(n)=910n−1​，那么有
$\sum_{i=1}^n\sum_{j=1}^m[\frac{10^{i^j}-1}{9}\%p==0]$i=1∑n​j=1∑m​[910ij−1​%p==0]
$$
考虑$\frac{10^n-1}{9}$910n−1​和$p$p的关系，先考虑$9$9和$p$p互质，那么可以变为
$(10^n-1)\cdot inv9\ \% p==0$(10n−1)⋅inv9 %p==0
由于互质$inv9\neq0$inv9̸​=0，所以只有
$10^n-1\ \% p==0$10n−1 %p==0
即
$10^n\equiv 1 (mod\ p)$10n≡1(mod p)
根据费马小定理，$10$10和$p$p互质有
$10^{phi(p)}\equiv 1(mod\ p)$10phi(p)≡1(mod p)
$10^{p-1}\equiv 1(mod\ p)$10p−1≡1(mod p)
由于$10^0\equiv 1(mod\ p)$100≡1(mod p)，那么循环节至少为$p-1$p−1，考虑是否有更小的循环节，根据同余式的性质
$a\equiv b(mod\ p)\rightarrow a^n\equiv b^n(mod\ p)$a≡b(mod p)→an≡bn(mod p)
那么令$d$d为$p-1$p−1的因子，即$d|p-1$d∣p−1，最小的循环节可能为$d$d
$(10^{d})^{\frac{p-1}{d}}\equiv 1(mod\ p)$(10d)dp−1​≡1(mod p)
所以我们可以对$p-1$p−1的因子进行检验得到最小的循环节$d$d，找到了最小的循环节$d$d之后我们如何求解答案呢。由于循环节为$d$d，所以$i^j$ij必须是$d$d的倍数。考虑$j$j是固定的，那么只要$i$i含有$d^{\left \lceil \frac{1}{j} \right \rceil}$d⌈j1​⌉的因子就可以了，令$g=d^{\left \lceil \frac{1}{j} \right \rceil}$g=d⌈j1​⌉，那么$1\sim n$1∼n中是$g$g的倍数的个数为$\frac{n}{g}$gn​。再考虑$g$g，我们可以将$d$d唯一分解了，那么就有
$d=p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots p_k^{a_k}$d=p1a1​​p2a2​​p3a3​​⋯pkak​​
$g$g就有
$g=p_1^{\left \lceil \frac{a_1}{j} \right \rceil}p_2^{\left \lceil \frac{a_2}{j} \right \rceil}p_3^{\left \lceil \frac{a_3}{j} \right \rceil}\cdots p_k^{\left \lceil \frac{a_k}{j} \right \rceil}$g=p1⌈ja1​​⌉​p2⌈ja2​​⌉​p3⌈ja3​​⌉​⋯pk⌈jak​​⌉​
随着$j$j的变化，$g$g的值也是变化的，设$maxn=max\{a_1,a_2,a_3,\cdots,a_k\}$maxn=max{a1​,a2​,a3​,⋯,ak​}，当$j$j的值为$1\sim maxn$1∼maxn时$g$g也就是随着变化的，我们分别计算每一个的贡献为$\frac{n}{g}$gn​，当$j>maxn$j>maxn时$g$g将不再变化贡献就为$\frac{n}{g}(m-maxn)$gn​(m−maxn)
这样就能统计出答案了，但是当$p=2,p=5$p=2,p=5时，虽然$9$9和$p$p互质但是$10^n\% p==0$10n%p==0，所以明显的答案都为$0$0
第二我们考虑$p=3$p=3的情况，由于$p=3$p=3于分母$9$9并不互质，所以我们并不能像上面那么做。考虑
$$
$\sum_{i=1}^n\sum_{j=1}^m[A(i^j)\%3==0]$i=1∑n​j=1∑m​[A(ij)%3==0]
由于$A(i^j)$A(ij)为长度为$i^j$ij连续的$1$1的整数，一个整数是否能被$3$3整除我们知道就是把各位上的数字加起来是$3$3的倍数就能整除了，令$A(i)$A(i)每一位上的和为$S$S，那么$A(i^j)$A(ij)每一位上的和就为$j\times S$j×S，由于$A$A上的每一位都是$1$1，所以$S=i$S=i，故最后的答案就是$n/3*m$n/3∗m

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long quickmod(long long a,long long b,long long mod=1e9+7)
{
    long long ans=1;
    while(b)
    {
        if(b%2==1)
            ans=ans*a%mod;
        b=b/2;
        a=a*a%mod;
    }
    return ans;
}
pair<int,int>a[1005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        long long p,n,m;
        scanf("%lld%lld%lld",&p,&n,&m);
        if(p==2||p==5)
        {
            printf("0\n");
            continue;
        }
        else if(p==3)
        {
            printf("%lld\n",n/3*m);
            continue;
        }
        long long x=p-1;
        int minn=p-1;
        for(int i=2; i*i<=x; i++)
        {
            if(x%i==0)
            {
                if(quickmod(10,i,p)==1)
                    minn=min(minn,i);
                if(quickmod(10,x/i,p)==1)
                    minn=min(1ll*minn,x/i);
            }
        }
        int cnt=0;
        int maxn=0;
        x=minn;
        for(int i=2; i*i<=x; i++)
        {
            if(x%i==0)
            {
                a[cnt].first=0;
                a[cnt].second=0;
                a[cnt].first=i;
                while(x%i==0)
                {
                    a[cnt].second++;
                    x=x/i;
                }
                maxn=max(a[cnt].second,maxn);
                cnt++;
            }
        }
        if(x>1)
        {
            a[cnt].first=0;
            a[cnt].second=0;
            a[cnt].first=x;
            a[cnt].second++;
            maxn=max(a[cnt].second,maxn);
            cnt++;
        }
        long long ans=0;
        long long g=1;
        for(int j=1; j<=min(1ll*maxn,m); j++)
        {
            g=1;
            for(int i=0; i<cnt; i++)
            {
                g=g*quickmod(a[i].first,ceil(1.0*a[i].second/j));
            }
            ans+=n/g;
        }
        if(m>maxn)
            ans+=n/g*(m-maxn);
        printf("%lld\n",ans);
    }
    return 0;
}