数论初级魔法大赏

最近在准备关于莫比乌斯反演的课件，准备把例题简要整理下来，那就开始吧

[1.bzoj 2190 SDOI2008]仪仗队

求2+∑x=1n−1∑y=1n−1[gcd(x,y)==1](n≤40000)2+\sum_{x=1}^{n-1}\sum_{y=1}^{n-1}[gcd(x,y)==1](n\le 40000)

最简单的做法，线性筛预处理出欧拉函数的前缀和，时间复杂度O(n)O(n)。

2.bzoj 2818 Gcd

求∑p∑x=1n∑y=1n[gcd(x,y)==p](n≤107)\sum_{p}\sum_{x=1}^{n}\sum_{y=1}^{n}[gcd(x,y)==p] (n\le 10^7)

其实就是∑p∑x=1⌊np⌋∑y=1⌊np⌋[gcd(x,y)==1]\sum_{p}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{n}{p}\rfloor}[gcd(x,y)==1]，枚举所有质数后就是和上一道题一样做法了，双倍经验。

[3.bzoj 2705 SDOI2012]Longge的问题

求∑i=1ngcd(i,n),n≤232\sum_{i=1}^{n}gcd(i,n), n\le 2^{32}

变形一下，枚举每种gcd的值，即

∑i=1ngcd(i,n)=∑d∣nd∑x=1nd[gcd(x,nd)==1]=∑d∣ndφ(nd)\begin{aligned} &\sum_{i=1}^{n}gcd(i,n) \\ =& \sum_{d\mid n}d \sum_{x=1}^{\frac{n}{d}}[gcd(x,\frac{n}{d})==1] \\ =& \sum_{d\mid n}d\varphi(\frac{n}{d}) \end{aligned}

那么根号枚举约数，单点求欧拉函数就做完了。

时间复杂度？是个经典的东西O(∑i=1ni+ni)=O(n34)O(\sum_{i=1}^{\sqrt{n}}\sqrt{i}+\sqrt{\frac{n}{i}})=O(n^{\frac{3}{4}})

[4.bzoj 2440 中山市选2011]完全平方数

求第k(k≤109)k(k\le 10^9)个不含完全平方数因子的正整数

二分答案，转为求前nn个数中有多少数不含完全平方因子。容斥一下，总数减去是4(2的平方)的倍数的，减去9的倍数，16的倍数不用管，前面减过了，再减去25的倍数，加上36的倍数，因为前面多减了一次…那这样就发现了容斥系数就是莫比乌斯函数。时间复杂度O(nlog⁡n)O(\sqrt{n}\log{n})

5.luogu P2257 YY的GCD(bzoj 2820)

求∑p∑x=1n∑y=1m[gcd(x,y)==p](n≤107)\sum_{p}\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)==p] (n\le 10^7)，T(≤10000)T(\le 10000)组询问

bzoj 2818的加强版，把其中一个n换成了m，这样就不能用欧拉函数了，推导一下：

下述的pp表示质数

∑p∑x=1n∑y=1m[gcd(x,y)==p]=∑p∑x=1⌊np⌋∑y=1⌊mp⌋[gcd(x,y)==1]=∑p∑x=1⌊np⌋∑y=1⌊mp⌋∑d∣gcd(x,y)μ(d)=∑p∑x=1⌊np⌋∑y=1⌊mp⌋∑d∣x∧d∣yμ(d)=∑p∑d=1⌊min(n,m)p⌋μ(d)⌊npd⌋⌊mpd⌋=∑k=1min(n,m)∑p,p∣kμ(kp)⌊nk⌋⌊mk⌋=∑k=1min(n,m)f(k)⌊nk⌋⌊mk⌋\begin{aligned} & \sum_{p}\sum_{x=1}^{n}\sum_{y=1}^{m}[gcd(x,y)==p] \\ =& \sum_{p}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{p}\rfloor}[gcd(x,y)==1] \\ =& \sum_{p}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{p}\rfloor}\sum_{d\mid gcd(x,y)}\mu(d) \\ =& \sum_{p}\sum_{x=1}^{\lfloor \frac{n}{p}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{p}\rfloor}\sum_{d\mid x \land d\mid y}\mu(d) \\ =& \sum_{p}\sum_{d=1}^{\lfloor \frac{min(n,m)}{p}\rfloor}\mu(d)\lfloor \frac{n}{pd}\rfloor\lfloor \frac{m}{pd}\rfloor \\ =& \sum_{k=1}^{min(n,m)}\sum_{p,p\mid k}\mu(\frac{k}{p})\lfloor \frac{n}{k}\rfloor\lfloor \frac{m}{k}\rfloor \\ =& \sum_{k=1}^{min(n,m)}f(k)\lfloor \frac{n}{k}\rfloor\lfloor \frac{m}{k}\rfloor \end{aligned}

其中第三行莫比乌斯反演，第五行交换求和，第六行令k=pdk=pd,转而枚举kk，化简到最后用筛法预处理出所有ff的值即可，这里应该可以用线性筛，不过懒得推导的话也可以枚举所有质数再枚举它的倍数这样求，那么时间复杂度就和埃氏筛一样了，之后每次求一组询问就是经典的数论分块了。时间复杂度O(nlog⁡log⁡n+Tn)O(n\log{\log{n}}+T\sqrt{n})。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10000000;
bool vis[N+5];
int prime[N+5],cnt;
int mu[N+5],f[N+5];
void getprime()
{
    mu[1]=1;
    for(int i=2;i<=N;i++)
    {
        if(!vis[i])
        {
            prime[cnt++]=i;
            mu[i]=-1;
        }
        for(int j=0;j<cnt && prime[j]<=N/i;j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j]) mu[i*prime[j]]=-mu[i];
            else
            {
                mu[i*prime[j]]=0;
                break;
            }
        }
    }
    for(int i=0;i<cnt;++i)
    {
        int x=prime[i];
        for(int j=x;j<=N;j+=x)
            f[j]+=mu[j/x];
    }
    for(int i=1;i<=N;++i)
        f[i]+=f[i-1];
}
ll calc(int n,int m)
{
    if(n>m) swap(n,m);
    ll ans=0;
    for(int i=1,j;i<=n;i=j+1)
    {
        j=min(n/(n/i),m/(m/i));
        ans+=1LL*(f[j]-f[i-1])*(n/i)*(m/i);
    }
    return ans;
}
int main()
{
    getprime();
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        printf("%lld\n",calc(n,m));
    }
}

6.spoj LCMSUM

求∑i=1nlcm(i,n),n≤106\sum_{i=1}^{n}lcm(i,n), n\le 10^{6}，T(≤300000)T(\le 300000)组询问。

∑i=1nlcm(i,n)=∑i=1ni×ngcd(i,n)=12∑i=1n−1n2gcd(i,n)+n=12∑d∣n,d≠nn2d∑k=1⌊nd⌋[gcd(k,nd)==1]+n=12n∑d∣n,d≠nndφ(nd)+n=12n∑d∣n,d≠1dφ(d)+n=12nf(n)+n\begin{aligned} & \sum_{i=1}^{n}lcm(i,n) \\ =&\sum_{i=1}^{n}\frac{i\times n}{gcd(i,n)}\\ =&\frac{1}{2}\sum_{i=1}^{n-1}\frac{n^{2}}{gcd(i,n)}+n\\ =&\frac{1}{2}\sum_{d\mid n,d\ne n}\frac{n^2}{d}\sum_{k=1}^{\lfloor \frac{n}{d}\rfloor}[gcd(k,\frac{n}{d})==1]+n \\ =&\frac{1}{2}n\sum_{d\mid n,d\ne n}\frac{n}{d}\varphi(\frac{n}{d})+n \\ =&\frac{1}{2}n\sum_{d\mid n,d\ne 1}d\varphi(d)+n \\ =&\frac{1}{2}nf(n)+n \end{aligned}

这样线性筛预处理完，O(nlog⁡n)O(n\log{n})的求出函数值ff，每次回答O(1)O(1)即可。

7.bzoj 2154 Crash的数字表格

求∑i=1n∑j=1mlcm(i,j),n,m≤107\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j),n,m\le 10^7

∑i=1n∑j=1mlcm(i,j)=∑i=1n∑j=1mijgcd(i,j)=∑d=1min(n,m)∑x=1⌊nd⌋∑y=1⌊md⌋dxy[gcd(x,y)==1]=∑d=1min(n,m)d∑x=1⌊nd⌋∑y=1⌊md⌋xy∑k∣x∧k∣yμ(k)=∑d=1min(n,m)d∑k=1⌊md⌋μ(k)∑x=1⌊ndk⌋∑y=1⌊mdk⌋k2xy=∑T=1min(n,m)∑k∣TkTμ(k)g(⌊nT⌋,⌊mT⌋)=∑T=1min(n,m)Tg(⌊nT⌋,⌊mT⌋)∑k∣Tkμ(k)=∑T=1min(n,m)Tg(⌊nT⌋,⌊mT⌋)f(T)\begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j) \\ =&\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{gcd(i,j)}\\ =&\sum_{d=1}^{min(n,m)}\sum_{x=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{d}\rfloor}dxy[gcd(x,y)==1] \\ =&\sum_{d=1}^{min(n,m)}d\sum_{x=1}^{\lfloor \frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{d}\rfloor}xy\sum_{k\mid x \land k\mid y}\mu(k) \\ =&\sum_{d=1}^{min(n,m)}d\sum_{k=1}^{\lfloor \frac{m}{d}\rfloor}\mu(k)\sum_{x=1}^{\lfloor \frac{n}{dk}\rfloor}\sum_{y=1}^{\lfloor \frac{m}{dk}\rfloor}k^{2}xy \\ =&\sum_{T=1}^{min(n,m)}\sum_{k\mid T}kT\mu(k)g(\lfloor \frac{n}{T}\rfloor,\lfloor \frac{m}{T}\rfloor)\\ =&\sum_{T=1}^{min(n,m)}Tg(\lfloor \frac{n}{T}\rfloor,\lfloor \frac{m}{T}\rfloor)\sum_{k\mid T}k\mu(k)\\ =&\sum_{T=1}^{min(n,m)}Tg(\lfloor \frac{n}{T}\rfloor,\lfloor \frac{m}{T}\rfloor)f(T) \end{aligned}

其中g(n,m)=∑i=1n∑j=1mij=n(n+1)2m(m+1)2g(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}ij=\frac{n(n+1)}{2}\frac{m(m+1)}{2}

一开始头铁，O(nlog⁡n)O(n\log{n})求的f(T)f(T)的值，超时无疑，然后学习了用线性筛求积性函数f(T)=∑k∣Tkμ(k)f(T)=\sum_{k\mid T}k\mu(k)的思路。

线性筛过程分两种情况讨论

1.primejprime_j整除ii，那么枚举i×primeji\times prime_j的约数kk时，如果关于primejprime_j的指数大于等于2的话莫比乌斯函数为零，对答案没有贡献，所以此时:

f(i×primej)=f(i)f(i\times prime_j)=f(i)

2.primejprime_j不整除ii，那么再分枚举的约数kk是否含有primejprime_j，不含有的部分就是f(i)f(i)，含primejprime_j的话，整体乘上这么多，并且莫比乌斯函数要变号，是−f(i)primej-f(i)prime_j。综上，此时:

f(i×primej)=(1−primej)f(i)f(i\times prime_j)=(1-prime_j)f(i)

这样这道题就做完了，时间复杂度O(n)O(n)。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=20101009;
const int N=10000000;
bool vis[N+5];
int prime[666666],cnt;
int f[N+5];
void getprime()
{
    f[1]=1;
    for(int i=2;i<=N;i++)
    {
        if(!vis[i])
        {
            prime[cnt++]=i;
            f[i]=(1-i+mod);
        }
        for(int j=0;j<cnt && i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=true;
            if(i%prime[j])
            {
                f[i*prime[j]]=1LL*(1-prime[j]+mod)*f[i]%mod;
            }
            else
            {
                f[i*prime[j]]=f[i];
                break;
            }
        }
    }
//    for(int i=1;i<=N;++i)
//    {
//        for(int j=i;j<=N;j+=i)
//        {
//            f[j]+=i*mu[i];
//            if(f[j]<0) f[j]+=mod;
//            else if(f[j]>=mod) f[j]-=mod;
//        }
//    }
}
int Sum(int n)
{
    return 1LL*(n+1)*n/2%mod;
}
int main()
{
    getprime();
    int n,m;
    scanf("%d%d",&n,&m);
    if(n<m) swap(n,m);
    ll ans=0;
    for(int i=1;i<=m;++i){
        ans+=1LL*i*Sum(n/i)%mod*Sum(m/i)%mod*f[i]%mod;
        if(ans>=mod) ans-=mod;
    }
    printf("%lld\n",ans);
}

[8.bzoj 3994 SDOI2015]约数个数和

求∑i=1n∑j=1md(ij),n,m≤50000\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij), n,m\le 50000，T(≤50000)T(\le 50000)组询问，其中dd是约数个数函数。

这个题一开始卡在一个结论上了，首先要知道d(ij)=∑x∣i∑y∣j[gcd(x,y)==1]d(ij)=\sum_{x\mid i}\sum_{y\mid j}[gcd(x,y)==1]，这个结论不好想，但可以用分解质因数的形式结合约数个数定理推出来，那解决了第一步，后面的就简单了。

∑i=1n∑j=1md(ij)=∑i=1n∑j=1m∑x∣i∑y∣j[gcd(x,y)==1]=∑i=1n∑j=1m∑x∣i∑y∣j∑k∣gcd(x,y)μ(k)=∑i=1n∑j=1m∑x∣i∑y∣j∑k∣x∧k∣yμ(k)=∑k=1min(n,m)μ(k)∑x=1⌊nk⌋∑y=1⌊mk⌋⌊nxk⌋⌊myk⌋=∑k=1min(n,m)μ(k)∑x=1⌊nk⌋⌊nxk⌋f(⌊mk⌋)=∑k=1min(n,m)μ(k)f(⌊nk⌋)f(⌊mk⌋)\begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)\\ =&\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}[gcd(x,y)==1]\\ =&\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}\sum_{k\mid gcd(x,y)}\mu(k)\\ =&\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}\sum_{k\mid x \land k\mid y}\mu(k)\\ =&\sum_{k=1}^{min(n,m)}\mu(k)\sum_{x=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{k}\rfloor}\lfloor\frac{n}{xk}\rfloor\lfloor\frac{m}{yk}\rfloor\\ =&\sum_{k=1}^{min(n,m)}\mu(k)\sum_{x=1}^{\lfloor\frac{n}{k}\rfloor}\lfloor\frac{n}{xk}\rfloor f(\lfloor\frac{m}{k}\rfloor)\\ =&\sum_{k=1}^{min(n,m)}\mu(k)f(\lfloor\frac{n}{k}\rfloor) f(\lfloor\frac{m}{k}\rfloor) \\ \end{aligned}

至此又可以数论分块搞定单组询问了，时间复杂度O(Tn)O(T\sqrt{n})。

9.bzoj 4659 lcm

化简下题意就是求∑i=1n∑j=1mlcm(i,j)[μ2(gcd(i,j))==1],n,m≤4000000\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)[\mu^2(gcd(i,j))==1],n,m\le 4000000，对2302^{30}取模，T(≤2000)T(\le 2000)组询问。发现就是在第七题的基础上加了个多组询问，且只统计μ2(gcd(i,j))==1\mu^2(gcd(i,j))==1的。

那么前面的推导都是一样的，最后化简到

原式=∑T=1min(n,m)g(⌊nT⌋,⌊mT⌋)T∑k∣Tkμ(k)μ2(Tk)=\sum_{T=1}^{min(n,m)}g(\lfloor \frac{n}{T}\rfloor,\lfloor \frac{m}{T}\rfloor)T\sum_{k\mid T}k\mu(k)\mu^2(\frac{T}{k})

头铁依然会TLE，还是先观察一下

f(T)=∑k∣Tkμ(k)μ2(Tk)f(T)=\sum_{k\mid T}k\mu(k)\mu^2(\frac{T}{k})是积性函数

且当TT分解质因数后的指数中有大于2的情况的话，显然此时f(T)=0f(T)=0，并且易知f(p)=1−p,f(p2)=−pf(p)=1-p,f(p^2)=-p，这样又可以线性筛搞一搞了，然后预处理出if(i)if(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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1<<30;
const int N=4000000;
bool vis[N+5];
int prime[N+5],cnt;
unsigned int f[N+5],sum[N+5];
void getprime() {
    f[1]=1;
    for(int i=2;i<=N;i++) {
        if(!vis[i]) {
            prime[cnt++]=i;
            f[i]=1U-i;
        }
        for(int j=0;j<cnt && i*prime[j]<=N;j++) {
            vis[i*prime[j]]=true;
            if(i%prime[j]) {
                f[i*prime[j]]=f[i]*f[prime[j]];
            }
            else {
                if(i==prime[j]) f[i*prime[j]]=-prime[j];
                else if(i/prime[j]%prime[j]==0) f[i*prime[j]]=0;
                else f[i*prime[j]]=f[i/prime[j]]*f[prime[j]*prime[j]];
                break;
            }
        }
    }
//    for(int i=1;i<=N;++i) {
//        for(int j=i;j<=N;j+=i) {
//            f[j]+=i*mu[i]*abs(mu[j/i]);
//        }
//    }
    for(int i=1;i<=N;++i)
        sum[i]=sum[i-1]+1U*i*f[i];
}
unsigned int Sum(int n)
{
    return 1LL*(n+1)*n/2;
}
int main()
{
    getprime();
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(n<m) swap(n,m);
        unsigned int ans=0;
        for(int i=1,j;i<=m;i=j+1){
            j=min(n/(n/i),m/(m/i));
            ans+=1U*(sum[j]-sum[i-1])*Sum(n/i)*Sum(m/i);
        }
        printf("%d\n",(int)(ans%mod));
    }
}

[10.bzoj 4816 Sdoi2017]数字表格

求∏i=1n∏j=1mf(gcd(i,j)),n,m≤106\prod_{i=1}^{n}\prod_{j=1}^{m}f(gcd(i,j)),n,m\le 10^6，其中ff为斐波那契数列，结果模109+710^9+7，T(≤1000)T(\le 1000)组询问。

∏i=1n∏j=1mf(gcd(i,j))=∏d=1min(n,m)f(d)∑i=1⌊nd⌋∑i=1⌊md⌋[gcd(i,j)==1]=∏d=1min(n,m)f(d)∑k=1min(⌊nd⌋,⌊md⌋)μ(k)⌊ndk⌋⌊mdk⌋\begin{aligned} &\prod_{i=1}^{n}\prod_{j=1}^{m}f(gcd(i,j)) \\ =&\prod_{d=1}^{min(n,m)}f(d)^{\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)==1]} \\ =&\prod_{d=1}^{min(n,m)}f(d)^{\sum_{k=1}^{min(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)}\mu(k)\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor}\\ \end{aligned}

这样指数部分是关于⌊nd⌋,⌊md⌋\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor的函数，可以分块，又因为外层是枚举的dd，所以分块套分块即可！时间复杂度O(T(n34+nlog⁡n))O(T(n^{\frac{3}{4}}+\sqrt{n}\log{n}))，前一部分来源分析同第三题。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
#define N 1000000
bool vis[N+5];
int prime[N+5],cnt;
int mu[N+5],sum[N+5];
int f[N+5],pre[N+5];
void getprime() {
    mu[1]=1;
    for(int i=2;i<=N;i++) {
        if(!vis[i]) {
            prime[cnt++]=i;
            mu[i]=-1;
        }
        for(int j=0;j<cnt && prime[j]<=N/i;j++) {
            vis[i*prime[j]]=true;
            if(i%prime[j])
                mu[i*prime[j]]=-mu[i];
            else {
                mu[i*prime[j]]=0;
                break;
            }
        }
    }
    for(int i=1;i<=N;++i)
        sum[i]=sum[i-1]+mu[i];
}
int power(int x,ll n){
    int ans=1;
    while(n){
        if(n&1) ans=1LL*ans*x%mod;
        x=1LL*x*x%mod;
        n>>=1;
    }
    return ans;
}
ll calc(int n,int m,int d){
    ll ans=0;
    for(int i=1,j;i<=n;i=j+1){
        j=min(n/(n/i),m/(m/i));
        ans+=1LL*(sum[j]-sum[i-1])*(n/i)*(m/i);
    }
    return ans;
}
int main(){
    getprime();

    pre[0]=pre[1]=f[1]=1;
    for(int i=2;i<=N;++i){
        f[i]=f[i-1]+f[i-2];
        if(f[i]>=mod) f[i]-=mod;
        pre[i]=1LL*pre[i-1]*f[i]%mod;
    }
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(n>m) swap(n,m);
        int ans=1;
        for(int i=1,j;i<=n;i=j+1){
            j=min(n/(n/i),m/(m/i));
            int x=1LL*pre[j]*power(pre[i-1],mod-2)%mod;
            ll y=calc(n/i,m/i,i);
            ans=1LL*ans*power(x,y)%mod;
        }
        printf("%d\n",ans);
    }
}
算法学习
#时间复杂度 #数论 #莫比乌斯反演
数论初级魔法大赏
https://izard.space/2019/06/05/数论初级魔法大赏/
作者
forever_you
发布于
2019年6月5日
许可协议