luoguP2231 [HNOI2002]跳蚤

题目链接

bzoj1220: [HNOI2002]跳蚤

题解

根据裴蜀定理，不定方程的解为未知数的gcd，所以选取的n个数的gcd为1
那么n - 1个数保证没有公约数为m的约数，枚举质因数容斥
质因数的个数上届是log的啊，我真傻，还想了半天QAq
那啥，bzoj高精，你们去做吧Qwq

代码

#include<cstdio> 
#include<algorithm> 
#define LL long long 
inline LL read() { 
    LL x = 0,f = 1; 
    char c = getchar(); 
    while(c < '0' || c > '9')c = getchar(); 
    while(c <= '9' && c >= '0')x = x * 10 + c - '0',c = getchar(); 
    return x * f; 
} 
const int maxn = 100007; 
LL ans = 0,n,m; 
LL pow(LL x,LL res) { 
    LL ret =  1; 
    for(;res;res >>= 1,x *= x) if(res & 1) ret *= x ;
    return ret; 
} 
int num = 0,rime[maxn]; 
void divede(int x) { 
    for(int i = 2;i * i <= x;++ i)  
        if(x % i == 0) { 
            rime[++ num] = i; 
            while(x % i == 0) x /= i; 
        } 
    if(x != 1) rime[++ num]  = x; 
} 
void solve(int cnt = 1,LL x = 1,int tp = 1) { 
    if(cnt == num + 1) { ans += (tp & 1) ? pow(m / x,n) : -pow(m / x,n); return ;} 
    solve(cnt + 1,x,tp); 
    solve(cnt + 1,x * rime[cnt],tp ^ 1);  
} 
int main() { 
    n = read(),m = read(); 
    //ans = 2 * pow(m,n); 
    divede(m); 
    solve(); 
    printf("%lld
",ans); 
    return 0; 
}