Problem

https://www.luogu.org/problemnew/show/P2231

Solution

见 SAC 课件。

针对因子的容斥似乎都不用考虑重复质因子的情况。

在不考虑重复质因子的情况下复杂度顶多只有 $2^{10}$ ，因此容斥效率是很高的。

考虑到莫比乌斯函数中出现了重复质因子的情况则判为 0。那么考虑原因是因为容斥状态只与 是否出现 有关。若有重复质因子不应当计入统计情况内。

// Code by ajcxsu
// Problem: jumper

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
int pri[50], p;
ll ans=0;
int ex[]={1, -1};

ll qpow(ll x, ll y) {
    ll ret=1;
    while(y) {
        if(y&1) ret=ret*x;
        x=x*x, y>>=1;
    }
    return ret;
}

ll n, m;
void dfs(int x, int k, ll tot) {
    if(x==p) ans+=ex[k&1]*qpow(m/tot, n);
    else {
        dfs(x+1, k+1, tot*pri[x]);
        dfs(x+1, k, tot);
    }
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    cin>>n>>m;
    ll nm=m;
    for(int i=2;i*i<=nm;i++) if(nm%i==0) {
        pri[p++]=i;
        while(nm%i==0) nm/=i;
    }
    if(nm>1) pri[p++]=nm;
    dfs(0, 0, 1);
    cout<<ans<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-luogu-2331.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆