步步高升

Description

春节的时候TENSHI去逛花市。她来到一个卖盆竹的摊位，看到一盆叫做“步步高升”的盆竹。“步步高升，步步高升……”学习就是要一步一步来，不能急，要打好基础。在稳固的基础上才谈得上步步高升！TENSHI若有所思。她看到这盆东西好意头，于是想买下。谁知一问价钱，“不贵不贵，才２ＸＸＲＭＢ。”TENSHI差点没昏倒，囊中羞涩嘛。但是TENSHI还是很想买下来，于是她就在一旁观察。观察了一段时间，她发现这个卖盆竹的人和别人杀价很有规律。设此人第i次报价为Wi元，那么他第i+1次报的价格为Wi－A或Wi －B。到了最后，TENSHI以Z元成交，高高兴兴的回家去了。
　　求TENSHI把盆竹的价格由W1元杀到Z元的方法总数。

Input

第一行有两个正整数W1和Z。第二行有两个正整数A和B。它们满足条件：
10 ≤ W1 ≤106，1 ≤ Z ≤ 106 ，Z < W1
2 ≤ A 、B ≤ 10000，A≠B

Output

方法总数
注意：结果不超过MAXLONGINT

Sample Input

样例1

256 88
5 9

样例2

100 10
13 23

Sample Output
样例１

3889832

样例２

0

解题思路

这道题的算法是搜索，使用搜索把a和b都减一遍，再把方案数记下来，最后输出

#include<iostream>
#include<iomanip>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn=10001;
long long m,n,ans=0,a,b;
void DFS(long long m)
{
   
	if(m==n)
	{
   
		ans++;//方案数加1
	}
	else if(m<n)
	{
   
		return;
	}
	else
	{
   
		m=m-a;DFS(m);m=m+a;//将a减一遍并回溯
		m=m-b;DFS(m);m=m+b;//将b减一遍并回溯
	}
}
int main()
{
   
	cin>>m>>n>>a>>b;
	DFS(m);
	cout<<ans; 
	return 0;
}