CTime_Pup_314

不能再颓废了

0%

20200225模拟赛

发表于 更新于 分类于 阅读次数： Valine：

div

首先我们有一个十分简单的式子

\[ \operatorname{E}(n)=\frac{1}{\sigma_0(n)}\sum_{d|n}E(d)+1 \]

其中 \(\sigma_0\) 为约数个数

化简之后得 \[ \operatorname{E}(n)=\frac{1}{\sigma_0(n)-1}\Big(\sum_{d|n,d\ne n}E(d)+\sigma_0(n)\Big) \]

复杂度为 \(\operatorname{O}(n)\) 显然过不了，但是这个式子其实告诉我们转移只与唯一分解质因子的指数集有关，而每次转移正好是一次高维前缀和

我们不需要表示出每一个数的指数集，我们只需要关注那些随质因子单调递增，指数非严格单调递增的数就好了，而这些数在 \(1\times10^{18}\) 中只有 \(172513\) 个，而与之有关的质因子也只有前 \(18\) 个，这些是可以通过 DFS 预处理出来的

我们将这些数按照转移顺序排序记第 \(i\) 个数 \(n\) 的期望为 \(f_i\)，那么我们考虑高维前缀和 \(s_{j,i}\) 表示第 \(i\) 个数满足前 \(0\) 到 \(j-1\) 个指数的大小与 \(n\) 相同，而剩下的指数小于等于其对应 \(n\) 的指数，根据这个我们列出方程

\[ s_{j,i}=s_{j+1,i}+s_{j,[\frac{n}{p_k}]} \]

这个式子前一部分的意思是 \(j\) 这一位不做改变，而后面的式子就是将 \(j\) 这一位的指数减 \(1\)，其中 \(k\) 是满足 \(c_j=c_k\) 最大的 \(k\)，这是由于我们需要满足指数非严格单调递减的条件，否则就搜不到，\(n\) 除以 \(p_j\) 和 \(p_k\) 在指数集的意义上是等价的

由于我们先有的 \(s_{j,i}\) 那么这时候 \(s_{0,i}\) 的意义就是 \(n\) 所有约数的期望和，直接转移可得 \(f_i\) 的值，最后将 \(f_i\) 的值更新所有的 \(s_{j,i}\) 即可

最后查询的话我们只有求出指数集，从大到小排序后即可找到其对应的等价的数

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
typedef long long i64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int P = 1e9+7, N = 172513+5, M = 19, p[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73}; const i64 B = 1e9;
struct num26
{
    i64 a, b;
    num26(i64 a = 0, i64 b = 0):a(a), b(b) {};
    int read() 
    {
        char s[30]; if(!~scanf("%s", s)) return -1;
        int n = strlen(s); reverse(s, s+n), a = 0, b = 0;
        for(int i = min(8, n-1); ~i; --i) a = a*10+s[i]-'0';
        for(int i = min(23, n-1); i > 8; --i) b = b*10+s[i]-'0';
        return 1;
    }
    friend bool operator < (num26 a, num26 b) { return a.b^b.b?a.b<b.b:a.a<b.a; }
    num26 friend operator + (num26 a, num26 b) { return num26((a.a+b.a)%B, a.b+b.b+(a.a+b.a)/B); }
    num26 friend operator * (num26 a, int b) { return num26(a.a*b%B, a.b*b+a.a*b/B); }
    num26 friend operator / (num26 a, int b) { return num26(((a.a%b)+(a.b%b)*B)/b, 0)+num26(a.a/b, a.b/b); }
    int friend operator % (num26 a, int b) { return (a.a%b+a.b%b*B%b)%b; }
    const void print(char c) const
    {
        if(b) printf("%lld%09lld", b, a); else printf("%lld", a);
        putchar(c); 
    }
};
const num26 oo(0, (i64)1e15);
int T, m, c[M], tot, s[M][N], f[N]; num26 n, w[N]; pair<num26, int> h[N];
int H(num26 n) { return h[lower_bound(h+1, h+1+tot, make_pair(n, 0))-h].second; }
void dfs(num26 n, int i, int pre)
{
    ++tot, h[tot] = make_pair(n, tot), w[tot] = n; if(oo < n*p[i]) return; n = n*p[i];
    for(int j = 1; j <= pre; ++j, n = n*p[i])
    { dfs(n, i+1, j); if(oo < n*p[i]) return; }
}
i64 inv(int i) { return i == 1?1:P-(P/i)*inv(P%i)%P; }
int main()
{
    freopen("div.in", "r", stdin), freopen("div.out", "w", stdout), dfs(num26(1, 0), 0, 90), sort(h+1, h+1+tot);
    for(int i = 2; i <= tot; ++i)
    {
        num26 n = w[i], m = w[i]; int sig = 1; 
        for(int j = 0; j < 18; ++j) 
        { while(m%p[j] == 0) m = m/p[j], ++c[j]; sig *= c[j]+1; }
        for(int j = 17, k; ~j; --j)
        {   
            for(k = j; k<17&&c[k+1] == c[j]; ++k);
            if(c[k]) s[j][i] = (s[j+1][i]+s[j][H(n/p[k])])%P;
        }
        f[i] = (s[0][i]+sig)*inv(sig-1)%P;
        for(int j = 0; j < 18; ++j) s[j][i] = (s[j][i]+f[i])%P, c[j] = 0;
    }
    while(~n.read())
    {
        m = read();
        for(int i = 0, p; i < m; ++i)
        { p = read(); while(n%p == 0) n = n/p, ++c[i]; }
        sort(c, c+m), reverse(c, c+m);  
        for(int i = 0; i < m; ++i) for( ; c[i]; n = n*p[i], --c[i]);
        printf("%d\n", f[H(n)]);
    }
    return 0;
}