Wuyanru's blog
0%

[BZOJ3512] DZY Loves Math IV

发表于 分类于 ，

做别的题遇到的部分分，稍微记一下吧。

题目链接。

题意

给定 ，求 的值。

。。

题解

考虑到 比较小，考虑枚举 那一位，然后计算后面这维的答案。

对于一个数字 ，令 。

则 ，。 这是一个递归的函数，递归边界是 或 ，而我们要求的是 。

考虑时间复杂度，对于 的情况，求的是 的前缀和，所以这部分总共是 的。

然后传入的时候 只有 种取值，除去初始情况传入的 的最高次数为 。

复杂度不会算。

代码

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
87
88
89
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
const int mod=1000000007;
const int L=1000000;
map<ll,ll>F;
vc<int>d[100001];
ll phi[1000001];
ll pre[1000001];
bool is[1000001];
int pri[1000001];
int wtf[100001];
int n,m;
inline void init()
{
    phi[1]=pre[1]=1;
    for(int i=2;i<=L;i++)
    {
        if(!is[i]) pri[++pri[0]]=i,phi[i]=i-1;
        for(int j=1;j<=pri[0]&&i*pri[j]<=L;j++)
        {
            is[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
        pre[i]=(pre[i-1]+phi[i])%mod;
    }
}
inline ll get(int n)
{
    if(n<=L) return pre[n];
    if(F.count(n)) return F[n];
    ll ans=(ll)n*(n+1)/2%mod;
    for(int l=2,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        ans-=get(n/l)*(r-l+1)%mod;
    }
    return F[n]=(ans%mod+mod)%mod;
}
map<pi,ll>G;
inline ll S(int k,int m)
{
    if(k==1) return get(m);
    if(m==1) return phi[k];
    if(!m) return 0;
    if(G.count(pi(k,m))) return G[pi(k,m)];
    int kp=wtf[k];ll ans=0;
    for(int i:d[kp]) (ans+=phi[kp/i]*S(i,m/i))%=mod;
    return G[pi(k,m)]=ans*k/kp%mod;
    // return G[pi(k,m)]=ans;
}
int main()
{
    init(),n=read(),m=read();
    for(int i=1;i<=n;i++) wtf[i]=1;
    for(int i=2;i<=n;i++) if(!is[i]) for(int j=i;j<=n;j+=i) wtf[j]*=i;
    for(int i=1;i<=n;i++) for(int j=i;j<=n;j+=i) d[j].push_back(i);

    ll ans=0;
    for(int i=1;i<=n;i++) (ans+=S(i,m))%=mod;
    printf("%lld\n",ans);
    return 0;
}