题意：规定每次跳的单位 a1, a2, a3 …… , an, M，次数可以为b1, b2, b3 …… bn, bn + 1, 正好表示往左，负号表示往右， 求能否调到左边一位，即 a1* b1+ a2 * b2 + a3 * b3 + …… + m * (bn + 1) = 1;
根据欧几里得，则a1, a2 a3 …… an, m 最大公约数为1，m已知且a1, a2, a3 …… an 均小于等于m, 一共有m ^ n可能， 将m 唯一分解之后， 假设m = 2 * 3 * 5, 则不大于m且包含2因子的 共 m / 2, 包含3的 为 m/ 3, 容斥
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int Max = + ;
typedef long long LL;
LL n, m;
int prime[Max + ], vis[Max + ], tot;
LL em[], a[], cnt;
LL res;
void getPrime()
{
tot = , cnt = ;
memset(vis, , sizeof(vis));
for (int i = ; i <= Max; i++)
{
if (!vis[i])
{
prime[tot++] = i;
for (int j = i; j <= Max / i; j++)
vis[i * j] = ;
}
} }
void getfactor(int b)
{
memset(em, , sizeof(em));
for (int i = ; i < tot; i++)
{
if (prime[i] > b)
break;
if (b % prime[i] == )
{
em[cnt++] = prime[i];
while (b % prime[i] == )
{
b /= prime[i];
}
}
}
if (b > )
em[cnt++] = b;
}
LL Pow(LL a, LL b)
{
LL ans = ;
while (b > )
{
if (b & )
ans *= a;
b >>= ;
a *= a;
}
return ans;
}
void dfs(int cur, int num, int Cnt) // cur当前位置， num当前已包含个数，Cnt目标个数
{
if (num == Cnt)
{
//达到目标个数时， 用 m 去除以 所有包含的数
LL u = m;
for (int i = ; i < num; i++)
u /= a[i];
res += Pow(u, n);
return;
}
for (int i = cur; i < cnt; i++)
{
a[num] = em[i];
dfs(i + , num + , Cnt);
}
return;
}
int main()
{
getPrime();
while (scanf("%I64d%I64d", &n, &m) != EOF)
{
getfactor(m);
LL sum = Pow(m, n);
for (int i = ; i <= cnt; i++) // 枚举每一个组合，i表示每个组合中数的个数
{
res = ;
dfs(, , i);
if (i & )
sum -= res;
else
sum += res;
}
printf("%I64d\n", sum);
} return ;
}