大概按这道题目来是这样。
有一只跳蚤站在钢丝中间，手上拿一张卡片，卡片上有 n 个数字再加一个数字 M。跳蚤每次挑卡片里一个数字，往左或者往右跳这么多距离。目标是跳到左边 1 格的地方捡到小礼物。问总共有多少种卡片，可以让跳蚤完成任务。
那我直接给一段代码。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
ll qp(ll a,ll b){
ll r=1;
while(b){
if(b&1)r*=a;
a*=a;
b>>=1;
}
return r;
}
int main(){
cin>>n>>m;
ll ans=0;
for(int i=1;i<=m;i++){
if(__gcd(i,m)==1) ans++;
}
cout<<qp(ans,n);
return 0;
}
可能懂了。
然后就再说也许有些人会懂了，感觉这不就是求和 M 互质的数有多少个，然后 n 次方就完事，样例输入 2 4，和 4 互质是 1、3 一共两个，2 的平方等于 4，哎？结果发现错了。
哈哈翻车现场，样例正确答案明明是 12，跑出来是 4，完全不对。
那就要讲正确思路和答案。
问题不是要求每个数字单独和 M 互质。
跳蚤来回跳，加减各个卡片数字，想凑出 1。数学老祖宗贝祖告诉我们，一堆数字加减能凑出 1 的条件，是这一整组数字的最大公约数等于 1，不是每一个数字分别跟 M 互质。
举例子，数字 2 和 3，单独看 2 和 3 不互质，但是 gcd (2,3)=1，它们加减可以凑出 1，3‑2=1。所以卡片里面是允许出现不跟 M 互质的数字，只要全部数搅在一起总的最大公约数是 1 就过关。
总方案是 M 的 n 次方，也就是前面 n 个数字每个都可以从 1 到 M 随便选。
我们用容斥来干掉那些不行的方案。不行的就是整套卡片全部都被 M 的某个质因子整除。
先把 M 拆出来所有不一样的质数因子。
枚举这些质数的全部组合，如果选了奇数个质数，就减掉全部数都是这些质数倍数的方案；选偶数个就加上。全部算完得到最终答案。
样例 n=2，M=4。M 的质因子只有 2。
总方案 44=16。
全部数字都是 2 的倍数的方案有 22=4。
16‑4=12，正好对上样例输出。
正确代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> fac;
ll n,m;
ll qpow(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1) res*=a;
a*=a;
b>>=1;
}
return res;
}
