Big Integer

Posted on | In , , ,

题目链接

题意

定义$A(n) = 11111..11$($n$个1)，计算

思路

显然当该模数是2或5无解。

我们去找一下这个东西的循环节$d$,易知.
枚举其所有因子，找到$d$，现在计算
分解，当确定$j$，那么有
这样就很好计算了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
  
const double    PI   = acos(-1.0);
const int       INF  = 0x3f3f3f3f;
const long long LINF = 1e18;
const long long MOD  = 1e9+7;
const int       MAXN = 1e5+10;
  
ll pri[105], fac[105], num = 0;
  
void uniqueDecompose(ll x)//唯一分解，pri为对应质数，fac为对应次数
{
    num = 0;//唯一分解后的质数个数
    for(int j = 2; j*j <= x; j++)
        if(x % j == 0)
        {
            pri[++num] = j, fac[num] = 0;
            while(x % j == 0) fac[num]++, x /= j;
        }
    if(x > 1) pri[++num] = x, fac[num] = 1;
}
  
ll qmul(ll x, ll y, ll m)
{
    ll res = 0;
    while(y)
    {
        if(y & 1) res = (res + x) % m;
        x = (x + x) % m;
        y >>= 1;
    }
    return res;
}
  
ll qpow(ll a, ll n, ll m)
{
    ll res = 1;
    while(n)
    {
        if(n & 1) res = qmul(res, a, m) % m;
        a = qmul(a, a, m) % m, n >>= 1;
    }
    return res;
}
  
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        //输入与特判
        ll p, n, m;
        scanf("%lld%lld%lld", &p, &n, &m);
        if(p == 2 || p == 5)
        {
            puts("0");
            continue;
        }
        //求循环节
        ll phi = 6 * (p - 1), d = LINF;//phi(9*p), 循环节
        assert(qpow(10, phi, 9ll*p) == 1);
        for(ll i = 1; i*i <= phi; i++)
            if(phi % i == 0)
            {
                ll fac1 = i, fac2 = phi / i;
                if(qpow(10, fac1, 9ll*p) == 1) d = min(d, fac1);
                if(qpow(10, fac2, 9ll*p) == 1) d = min(d, fac2);
            }
        //求有多少对ij使得d|i^j(i的j次方)
        uniqueDecompose(d);
        ll g = 1, ans = 0;
        for(ll i = 1; i <= min(m, 30ll); i++)
        {
            g = 1;
            for(int j = 1; j <= num; j++)
                g *= qpow(pri[j], ceil(1.0*fac[j]/i), 2e9);
            ans += n / g;
        }
        if(m > 30) ans += (m - 30) * (n / g);
        printf("%lld\n", ans);
    }
    return 0;
}

0%