思想如下：

1.易证，可以完成任务的充要条件为n+1个数的最大公约数为1。
> 2.若m为质数，则除了n+1个m的情况外，都可完成任务，即有(m^n)-1种情况。
> 3.若m为合数，则可能的最大公约数必为m的质因数的倍数。可以算出所有最大公约数的质因数含p的情况有(m/p)^n种。
> 4.设m的质因数为a1,a2,...,aT。则最大公约数不为1的所有情况数为(1<=i1<=T)∑((m/ai1)^n)- (1<=i1<i2<=T)∑((m/(ai1*ai2))^n)+…-(-1)^(T-1)*(1<=i1<i2<…<i(T-1)<=T)∑((m/(ai1*ai2*…*ai(T-1)))^n)-(-1)^T* (1<=i1<i2<…<iT<=T)∑((m/(ai1*ai2*…*aiT))^n)。用m^n减去所有情况数即是可完成任务数。



#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;
 }
}

• Re:这个程序我没有用__int64 ，用的long 老师TLE，郁闷哪！！请各位执教一下吧 (1312) 061408147 2009-11-26 11:13:23