> 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减去所有情况数即是可完成任务数。


你的公式没有完全看懂 但是似乎有一点容斥原理的感觉 不知道是不是？