题目链接
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5057
题意
给出两个数 递推式是 |s[i - 1] - s[i - 2]|
然后求这个数列 出现的不同数字的个数
思路
因为 X 和 Y 是整数
那么 我们可以理解为
Y = aX + b
也就是说 会是这样一个数列
(aX + b) (x) ((a - 1) X + b) ((a - 2)X + b) x b
然后 我们发现 最后的 x b
是一个递归的子问题
可以把 x b 看成新的 x y
递归下去
我们发现出口 实际上是 b == 0 的时候
然后对于每一次的迭代 答案都是 (kx + b) / x 也就是 k
当 b 等于0 的时候 迭代结束 答案要加上1 以为最后的0 是没有加上的
然后注意一下 当 给出的初始数字 存在0的时候 要讨论一下
AC代码
#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define CLR(a, b) memset(a, (b), sizeof(a)); #define pb push_back #define bug puts("***bug***"); #define fi first #define se second #define L(on) (on<<1) #define R(on) (L(on) | 1) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define syn_close ios::sync_with_stdio(false); cin.tie(0); #define sp system("pause"); #define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef long double ld; typedef pair <int, int> pii; typedef pair <ll, ll> pll; typedef pair <string, int> psi; typedef pair <string, string> pss; typedef pair <double, int> pdi; const double PI = acos(-1.0); const double EI = exp(1.0); const double eps = 1e-8; const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fll; const int maxn = (int)1e5 + 10; const ll MOD = (ll)1000000000; int main() { int t; cin >> t; for (int tt = 1; tt <= t; tt++) { printf("Case #%d: ", tt); ll n, m; scanf("%lld%lld", &n, &m); if (n == 0 || m == 0) printf("%d\n", n == m ? 1 : 2); else { ll ans = 1; if (n < m) swap(n, m); while (m) { ans += n / m; ll tmp = m; m = n % m; n = tmp; } printf("%lld\n", ans); } } }转载于:https://www.cnblogs.com/Dup4/p/9433068.html
相关资源：JAVA上百实例源码以及开源项目