分析：其实就是看能否有一组解x1，x2, x3, x4....xn+1,使得sum{xi*ai} = 1,也就是只要有任意一个集合{ai1,ai2,ai3, ...aik|gcd(ai1, ai2, ai3...aik) = 1} ,也就是要求gcd(a1, a2, a3...an+1) = 1.an+1一定为M，那么前面n个数总共M^n种方案，减去gcd不为1的，也就是减去gcd为奇数个素数的乘积的情况，加上偶数个素数的乘积的情况。
代码：
1 #include <cstdio> 2 #include <iostream> 3 #include <map> 4 #include <cstring> 5 #include <cstdlib> 6 #include <cmath> 7 #include <vector> 8 #define pb push_back 9 #define mp make_pair 10 #define esp 1e-8 11 #define lson l, m, rt<<1 12 #define rson m+1, r, rt<<1|1 13 #define sz(x) ((int)((x).size())) 14 #define pb push_back 15 #define in freopen("solve_in.txt", "r", stdin); 16 #define out freopen("solve_out.txt", "w", stdout); 17 18 #define bug(x) printf("Line : %u >>>>>> ", (x)); 19 #define inf 0x7f7f7f7f 20 using namespace std; 21 typedef long long LL; 22 typedef map<int, int> MPS; 23 typedef pair<int, int> PII; 24 25 const int maxn = 211; 26 const int B = 10000; 27 struct BigInt{ 28 int dig[maxn], len; 29 BigInt(int num = 0):len(!!num){ 30 memset(dig, 0, sizeof dig); 31 dig[0] = num; 32 } 33 int operator [](int x)const{ 34 return dig[x]; 35 } 36 int &operator [](int x){ 37 return dig[x]; 38 } 39 BigInt normalize(){ 40 while(len && dig[len-1] == 0) 41 len--; 42 return *this; 43 } 44 void output(){ 45 // cout << len << endl; 46 47 if(len == 0) puts("0"); 48 else { 49 printf("%d", dig[len-1]); 50 for(int i = len-2; i >= 0; i--) 51 printf("%04d", dig[i]); 52 } 53 puts(""); 54 } 55 }; 56 BigInt operator * (BigInt a, BigInt b){ 57 BigInt c; 58 c.len = a.len+b.len+1; 59 for(int i = 0; i < a.len; i++) 60 for(int j = 0, delta = 0; j < b.len+1; j++){ 61 62 delta += a[i]*b[j]+c[i+j]; 63 c[i+j] = delta%B; 64 delta /= B; 65 } 66 // c.normalize().output(); 67 return c.normalize(); 68 } 69 BigInt operator + (BigInt a, BigInt b){ 70 71 BigInt c; 72 c.len = max(a.len, b.len)+1; 73 for(int i = 0, delta = 0; i < c.len; i++){ 74 delta += a[i]+b[i]; 75 c[i] = delta%B; 76 delta /= B; 77 } 78 return c.normalize(); 79 } 80 BigInt operator - (BigInt a, BigInt b){ 81 BigInt c; 82 c.len = a.len; 83 for(int i = 0, delta = 0; i < c.len; i++){ 84 delta += a[i]-b[i]; 85 c[i] = delta; 86 delta = 0; 87 if(c[i] < 0){ 88 delta = -1; 89 c[i] += B; 90 } 91 } 92 return c.normalize(); 93 } 94 vector<PII> arr; 95 int getNum(int x) { 96 int ans = 0; 97 for(int i = 2; i*i <= x; i++) { 98 if(x%i == 0) { 99 x /= i; 100 ans++; 101 if(x%i == 0) return 0; 102 } 103 } 104 if(x != 1) ans++; 105 return ans; 106 } 107 BigInt getPow(int x, int y){ 108 BigInt res = 1; 109 BigInt c; 110 int len = 0; 111 while(x){ 112 c[len] = x%B; 113 c.len = max(c.len, ++len); 114 x /= B; 115 } 116 while(y){ 117 if(y&1) res = res*c; 118 c = c*c; 119 y >>= 1; 120 } 121 return res; 122 } 123 int main() { 124 125 // BigInt x = getPow(2, 1); 126 // x.output(); 127 128 int n, m; 129 while(scanf("%d%d", &n, &m) == 2) { 130 BigInt ans = getPow(m, n); 131 // ans.output(); 132 int y = m; 133 arr.clear(); 134 for(int i = 1; i*i <= y; i++) if(y%i == 0) { 135 int tmp = getNum(i); 136 if(tmp) { 137 arr.pb(PII(i, tmp)); 138 } 139 if(y/i != i) { 140 tmp = getNum(y/i); 141 if(tmp) { 142 arr.pb(PII(y/i, tmp)); 143 } 144 } 145 } 146 for(int i = 0; i < sz(arr); i++){ 147 int x = arr[i].first; 148 int y = arr[i].second; 149 BigInt tmp = getPow(m/x, n); 150 if(y&1) ans = ans - tmp; 151 else ans = ans + tmp; 152 } 153 ans.output(); 154 } 155 return 0; 156 }