扩展欧几里得：ax+by=gcd(a,b) 一定有解

能跳到左边一格，即ax+by=-1 

若a，b的gcd=1，则一定有解

所以问题转化为

求n个不大于m的数，他们与m的gcd=1 的方案数

容斥原理

把m分解质因数

枚举质因数，若他们的乘积=x

即当前n个数与m的gcd是x的倍数

x的倍数由m/x个，所以当前序列有（m/x）^ n

ans=m^n-（m/x1）^n + (m/x2) ^n - ……

 

没写高精度

 

#include
     
      #include
      
       typedef long long LL;int sum,p[30];LL pow(LL a,LL b){    LL res=1;    for(;b;a*=a,b>>=1)        if(b&1) res*=a;    return res;}int main(){    LL n,m;    scanf("%lld%lld",&n,&m);    LL k=m;    for(int i=2;i*i<=k;++i)        if(!(k%i))        {            p[++sum]=i;            while(k%i==0) k/=i;        }    if(k>1) p[++sum]=k;    int s=1<