2013 - 同余问题
给n个数，现在想知道有多少个大于1的整数被这n个数除得到的余数相同，请你帮他~
Input
第一个数为T，表示case数，
每个case第一行输入一个2<=n<=100，表示数字个数
之后输入n个数，每个数都小于10^9。
Output
每个case输出一个数，表示大于1且满足除这n个已给出的数结果余数相同的数的个数。
Examples
Input
2 3 6 34 38 5 5 17 23 14 83
Output
2 1
Hint
第一个样例三个数除以2都余0，除以4都余2，所以符合条件的有两个数。
Solution C++
#include <bits/stdc++.h> using namespace std; int T, n, a[109], b[109]; int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); } int main() { cin >> T; while (T --) { cin >> n; for (int i = 1; i <= n; i ++) cin >> a[i]; sort(a + 1, a + 1 + n); for (int i = 2; i <= n; i ++) b[i - 1] = a[i] - a[i - 1]; int x = b[1]; for (int i = 1; i < n; i ++) { x = gcd(x, b[i]); } int t = sqrt(x), ans = 0; for (int i = 1; i <= t; i ++) { if (x % i == 0) { ans += 2; } } if (t * t == x) { ans --; } cout << ans - 1 << endl; } return 0; }
Hint
第一个样例三个数除以2都余0，除以4都余2，所以符合条件的有两个数。