GCD application
这道题目 如果是 搜索做，主要一个限制条件判断就是A1*…Ak是否是M整数倍，这里看到某大神代码用了这样
一个递推关系来判定，解决了大整数 溢出的问题
P(i)=(j=i->n) GCD(P(i-1)j, m), 最后判P[k]==m 等价于 A1…Ak是否是M的倍数。
具体的证明都是马后炮了，在限时的比赛里几乎没用，重要的是会有一种称为数感的东西，大致是这样，然后
模拟点数据验证一下。
试着推导了一下，P(i)=gcd(P(i-1)Ai, m)=….=gcd(A1,m)….gcd(Ak,m)
而gcd(A1,m)….gcd(Ak,m)<====>A1…Ak%m==0
gcd有如下性质
gcd(a, b)<=min(a, b)
gcd(ab, c)=gcd(a, c)gcd(b, c)
具体代码如下，自己不知道这个方法的时候，做了质因数分解，然后hash存，每次还要hash减，dfs调用后还要复原，又称为回溯
这题有个DP做法更优，但是先实现这个再说
int n,m;
int solve(int now_pos,int lft,int lcm){
if(lft == 0){
if(lcm == m)return 1;
return 0;
}
int cnt=0;
for(int i=now_pos;i<=lft;i++){
cnt+=solve(i+1,lft-i,__gcd(lcm*i,m));
}
return cnt;
}