题目描述

已知a[1],a[2]

a[i]=abs(a[i-1]-a[i-2])  (i>=3)

问数列中出现了多少种不同的数。

样例输入

3 5

样例输出

5

提示

 

 

题解

这道题给你a[1]，a[2],要你求数列中有多少种不同的数

通过几个数据的手算不难发现a[1]和a[2]互换 答案是一样的

具体答案就是一个辗转相除法，我们可以用dfs来做

每次ans+=x/y;(x>y)

 

然后判断x%y==0(当a[i]==0的时候数列中的数才不会重复)else dfs(y,x%y);

最后输出ans+1即可(为什么要加一因为刚开始的时候你没有加上a[1])

1 #include
       
         2 #define ll long long 3 using namespace std; 4 ll n,m,ans; 5 void dfs(ll a,ll b){ 6     ans+=a/b; 7     if (!(a%b)) return; else dfs(b,a%b);  8 } 9 int main(){10     scanf("%lld%lld",&n,&m);11     if (n