「NewCode 2019-3」 E. Big Integer

For little pupils, a very large number usually means an integer with many many digits. Let's define a class of big integers which consists only of the digit one $(11 \cdots 1)$ . The first few integers in this class are $1, 11, 111, 1111 \cdots$ . Denote $A(n)$ as the $n$ -th smallest integer in this class. To make it even larger, we consider integers in the form of $A(a^b)$
. Now, given a prime number $p$ , how many pairs $(i, j)$ are there such that 1 $\leq i \leq n,\ 1 \leq j \leq m,\ A(i^j) \equiv 0(mod \ p)$

The input contains multiple cases. The first line of the input contains a single integer $T(1 \le T \le 100)$ , the number of cases.
For each case, the input consists of a single line, which contains 3 positive integers $p, n, m \ (p, n, m \leq 10^9)$ .

链接🔗

题解

化简等式
$(11 \cdots 1) =(\frac{10^n - 1}{9}\equiv 0 (mod \ p)) = (10^n \equiv 1 (mod \ 9p))$

根据 $Bezout$ 定理 , 线性同余方程有解，当且仅当 $gcd(10^n,9p)|1$

当 $2|p,5|p$ 时，显然无解，输出 $0$ 即可

否则根据欧拉定理, $10^n \equiv 1 (mod \ 9p) = 10^{\phi(9p)} \equiv 1 (mod \ 9p)$

因此我们需要找到 $10^i mod \ 9p$ 的循环节 $d$ ，也就是最小正整数解

根据欧拉定理推论：若 $a,n$ 互质，则满足 $a^x \equiv 1 (mod \ n)$ 的最小正整数解 $x_0$ 是 $\phi(n)$ 的约数。

因为 $n < 1e9$ ，所以直接暴力枚举 $\phi(n)$ 的约数，用快速幂进行验证是否正确即可

接下来我们统计有多少 $i,j$ 满足 $d|i^j$ 即可

根据算术基本定理， $d | i^j = \prod_{i}^n p_{i}^{k_i} | i^j$

考虑枚举 $j$ ,则 $i$ 必须是 $g = \prod_{i}^n p_{i}^{\left \lceil \frac{k_i}{j} \right \rceil}$ 的倍数，则数量为 $\frac{n}{g}$

由于 $\sum k_i <=30$ ，所以我们仅需枚举到30即可，对于30以上的部分， $g$ 值唯一

$Ps$ 本题可能卡64位精度，建议在快速幂过程中，用快速乘代替基础乘运算

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
long long t,n,m,p;
const long long inf = 1e18;
long long phi(long long x)
{
    long long ans = x;
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            ans = ans/i *(i-1);
            while(x%i == 0) x/=i;
        }
    }
    if(x>1) ans = ans/x * (x-1);
    return ans;
}
long long pow(long long a,long long b, long long mod)
{
    long long ans = 1ll;
    while(b)
    {
        if(b&1) ans = mul(ans,a,mod);
        a = a*a%mod;
        b>>=1;
    }
    return ans;
}
long long find(long long x)
{
    long long ans = x;
    for(long long i = 1;i*i<=x;i++)
    {
        if(x%i==0)
        {
            if(pow(10,i,9*p) == 1) ans = min(ans,i);
            if(pow(10,x/i,9*p) == 1) ans = min(ans,x/i);
        }
    }
    return ans;
}
long long pri[50],c[50],tot;
void divide(long long n)
{
    tot = 0;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i == 0)
        {
            pri[++tot] = i,c[tot]=0;
            while(n%i==0) c[tot]++, n/=i;
        }
    }
    if(n>1) pri[++tot] = n ,c[tot]=1;
}
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld %lld %lld",&p,&n,&m);
        if(p%2==0||p%5==0)
        {
            printf("0\n");
            continue;
        }
        long long d = find(phi(9*p));
        //printf("%lld \n",phi(9*p));
        divide(d);
        long long ans = 0ll;
        for(int j=1;j<=min(m,30ll);j++)
        {
            long long g =1ll;
            for(int i=1;i<=tot;i++)
                g *=  pow(pri[i],((c[i]-1)/j+1),inf);
            ans += n/g;
        }
        long long g = 1ll;
        for(int i=1;i<=tot;i++) g*=pri[i];
        if(m>30)
        ans += (long long) (m-30) * (n/g);
        printf("%lld\n",ans);
    }
    return 0;
}

dinnerhunt

「NewCode 2019-3」 E. Big Integer

链接🔗

题解

代码