一共有 m ^ n 种，
我们计算有多少个n元组，不满足条件。
如果不满足条件，这 (n + 1)张牌的面值中任意选两个a[i],a[j],(i<>j),记为a,b
那么不定方程 a * x + b * y = 1 无解（否则可以完成任务）。由不定方程的知识，无解的必要条件就是这n + 1个数任意选择两个都互质，也就是说这n + 1个数的最大公约数是1。
关于充分性：
如果这n + 1个数的最大公约数是d,d > 1
任意一种取牌方案，x[i]表示第i种牌取了多少。sigma(a[i] * x[i])是最后的移动步数，它是d的倍数，不为1，得证。

也就是我们要找有多少种取n个数的方法，使得这n个数和m的最大公约数不是1
可以枚举得出m有多少个不同的质因数，m = pi (yi ^ pi),不同的因数是yi,pi表示它的指数，比如 360 = (2 ^ 3) * (3 ^ 2) * (5 ^ 1)
然后应用容斥原理，
举例来说，m = 360, 有 2，3，5这3个不同的质因数
答案 = (m ^ n) - （有公因数2的n元组）- （有公因数3的n元组）- （有公因数5的n元组）+ （有公因数2，3的n元组） -（有公因数2，5的n元组） - （有公因数3，5的n元组）+ （有公因数2，3，5的n元组）。这个比公式形象些。

有公因数d的n元组，每个位置上有 (m/d)个选择（1 ~ m里面有m/d个d的倍数），根据乘法原理，可以得出有公因数d的n元组有 (m/d)^n 个。

有了上面这些，最后就是实现的问题了。我个人一般dfs所有的情况，写个for循环也可以，鉴于本人IQ问题，就不使用位运算。了下面贴个伪代码:
void dfs(int dep,int sum,int per)
{
     if (dep == a.size())
     {
        if (!sum) return;
        bigint tmp(1);
        for (int i = 1;i<=n;i++) tmp *= per;
        //tmp.out();
        if (sum & 1) answer -= tmp;
        else answer += tmp;  
        return;
     }
     b[dep] = 1;
     dfs(dep + 1,sum + 1,per / a[dep]);
     b[dep] = 0;
     dfs(dep + 1,sum,per);
}
per代表每一位上可能的选择数，这个代码加个高精度模板就行了

对了，随便给个数据
5 99999997
9999998500000087275414221566804671288000
1 2 3 4 ..... 好像超过long long了

这么水的题目WA了很久，写个报告纪念一下。