> 思想如下：
> 
> 1.易证，可以完成任务的充要条件为n+1个数的最大公约数为1。
> 
> 
> 
> #include <iostream.h>
> #include <math.h>
> #define maxm 100000000
> long p[20];
> long s[20];
> long sum = 0;
> int COUNT =0;
> long M=0;
> long N=0;
> long getsum(int m){
> int i=1;
> long temp=M;
> for(i=1;i<=m;i++){
> 	temp/=p[s[i]];
> }
> temp=(long)pow(temp,N);
> return temp;
> }
> 
> void zuhe(int x,int y,int m){
> 	if(y<=m){
> 	int i;
> 	for(i=x;i<=COUNT-m+y;i++){
> 	s[y]=i;
> 	if(y==m){sum+=getsum(m);}
> 	else zuhe(x+1,y+1,m);
> 	x++;//为了改变上一步else zuhe(x+1,y+1);
> 	    //只是改变x，并没有改变y；
> 	}
> 	}
> }
> 
> 
> void main(){
> long m,mm;
> long n;
> int count = 0;
> cin>>n>>m;//对m进行分解
> mm = m;
> long i=1;
> long temp = 1;
> if(m==1){cout<<"1"<<endl;}
>  else{
>     for(i=2;i<=mm;i++){
> 	    if(m%i==0){
> 	      if(i!=temp){
> 	       count++;
> 	       p[count] = i;
> 	       temp = i;
> 		  }
> 	      m/=i;
> 		  if(m==1){break;}
> 	      i--;//例如8的质因数是2，2，2，我们必须
>         //连续3次检测2是否是他的质因数
> 		}
> 	}
>   N = n;M =mm;COUNT = count;
>   long temp = 0;
>   long SUM=0;
>      for(i=1;i<=count;i++){
>      zuhe(1,1,i); 
>      temp = sum;
> 	 sum=0;
>      SUM+=((long)pow(-1,i-1)*temp);
> 	 }
>  long gogo = (long)pow(mm,n);
>   cout<<(gogo-SUM)<<endl;
>  }
> }