容斥原理——poj1091

将m质因子分解，然后枚举选取的质因子个数i进行容斥，每种情况进行一次dfs即可

dfs结束标记：当质因子个数达到i时退出递归，同时累加该解对应的方案数

/*
给定n,m
共有n个数的数组a，不超过m
m^n减掉 gcd(a)>1的情况
先把m质因数分解
然后枚举不同的质因子个数即可
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define ll long long ll n,m,p[],mm,ans,sum;ll Pow(ll a,ll b){
    ll res=;
    while(b){
        if(b%)res=res*a;
        b>>=;a=a*a;
    }
    return res;
}
void divide(){
    mm=;ll tmp=m;
    for(int i=;i*i<=m;i++)
        if(tmp%i==){
            p[++mm]=i;
            while(tmp%i==)tmp/=i;
        }
    if(tmp>)p[++mm]=tmp;
}int a[];//临时数组用来存用到的质因子
void get_sum(int pos,int cnt,int num){
    if(cnt>num){//搜出了一组解
        ll tmp=m;
        for(int i=;i<cnt;i++)tmp/=a[i];
        sum+=Pow(tmp,n);
        return;
    }
    for(int i=pos;i<=mm;i++)//枚举下一个位置
        a[cnt]=p[i],get_sum(i+,cnt+,num);
}int main(){
    while(cin>>n>>m){
        ans=Pow(m,n);
        divide();//分解质因子m
        for(int i=;i<=mm;i++){
            sum=;
            get_sum(,,i);
            if(i&) ans-=sum;//关于质因子个数的容斥
            else ans+=sum;
        }
        cout<<ans<<endl;
    }
}