一道簡單的數論題,但因為自己的一點原因,wa了5次。
題目連結:https://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了多少次,重新寫就好了。有些事卻不是這樣。