计蒜客 – 45284 数对 题解
一道简单的数论题,但因为自己的一点原因,wa了5次。
题目链接://nanti.jisuanke.com/t/45284
给出一对(a, b)和一个 k 。如果只能恰好整除(a, b)中的一个的正整数的个数大于等于k,输出Yes。
只需要求出 (a的因子数) + (b的因子数),
再减去(a和b的最大公因数的因子数)* 2 。
就能求出 a 和 b 的所有不公共因子个数了,下面是AC代码。
#include <iostream> #include <algorithm> #include <cstring> #include <string> #include <cmath> #include <map> typedef long long ll; using namespace std; ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); } int main() { freopen("pair.in", "r", stdin); freopen("pair.out", "w", stdout); int t; cin >> t; while (t--) { ll a, b, k; cin >> a >> b >> k; int cnt = 0; // 保存 a 和 b 的因子数之和 int cntc = 0; // 保存 gcd(a,b) 的因子数 if (a == b) cnt = 0; // 如果 a == b,肯定没有满足条件的因子,直接cnt = 0,跳过 else if (b % a == 0) cnt = 0; // 如果 a 是 b 的因子,也不会有满足条件的因子,cnt = 0, 跳过 else { // 因为因子成对出现,例如 12 % 2 == 0,就得到了 2 和 6,所以试除到( 根号a )即可 for (ll i = 1; i * i <= a; i++) { if (a % i == 0 && a / i == i) cnt++; // 重复的只算一次,例如 9 = 3 * 3,只算一个3 else if (a % i == 0) cnt += 2; } for (ll i = 1; i * i <= b; i++) { if (b % i == 0 && b / i == i) cnt++; else if (b % i == 0) cnt += 2; } ll t = gcd(a, b); for (ll i = 1; i * i <= t; i++) { if (t % i == 0 && t / i == i) cntc++; else if (t % i == 0) cntc += 2; } cnt = cnt - 2 * cntc; // 公共因子在 a, b 中都出现了,所以要减去2倍 } if (cnt >= k) cout << "Yes" << endl; else cout << "No" << endl; } return 0; }
题目wa了多少次,重新写就好了。有些事却不是这样。