Description
今天西片同学又被高木同学捉弄了，高木同学跟西片同学玩了这么一个游戏。两人心中分别想一个数字，这两个数字分别为x和y （1<=x,y<=1e18） ，然后让西片同学说出一共有多少个整数既是x的因子，又是y的因子。由于西片和高木很有默契，所以保证他们两个想的数x和y的最大公因数不会超过1e9。这个问题又难住了西片同学了，你能帮帮西片同学告诉他答案吗？
Input
数据占一行，包含两个整数x和y（1<=x,y<=1e18），保证gcd（x,y）<=1e9。
Output
输出既是x因子又是y因子的整数的个数。输出占一行
Accepted Code(暴力)
#include <bits/stdc++.h>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
long long a, b;
cin >> a >> b;
{
int maxm = __gcd(a, b);
int cnt = 0;
for (int x = 1; x * x <= maxm; x++) //小优化，o(n根号2)
{
if (maxm % x == 0)
++cnt;
}
if (sqrt(maxm) == (int)sqrt(maxm))
{
cnt = 2 * cnt - 1;
}
else
{
cnt *= 2;
}
cout << cnt << endl;
}
return 0;
}- #include <bits/stdc++.h>
- using namespace std;
- int main()
- {
- std::ios::sync_with_stdio(false);
- long long a, b;
- cin >> a >> b;
- {
- int maxm = __gcd(a, b);
- int cnt = 0;
- for (int x = 1; x * x <= maxm; x++) //小优化，o(n根号2)
- {
- if (maxm % x == 0)
- ++cnt;
- }
- if (sqrt(maxm) == (int)sqrt(maxm))
- {
- cnt = 2 * cnt - 1;
- }
- else
- {
- cnt *= 2;
- }
- cout << cnt << endl;
- }
- return 0;
- }
#include <bits/stdc++.h>
using namespace std;
int main()
{
std::ios::sync_with_stdio(false);
long long a, b;
cin >> a >> b;
{
int maxm = __gcd(a, b);
int cnt = 0;
for (int x = 1; x * x <= maxm; x++) //小优化，o(n根号2)
{
if (maxm % x == 0)
++cnt;
}
if (sqrt(maxm) == (int)sqrt(maxm))
{
cnt = 2 * cnt - 1;
}
else
{
cnt *= 2;
}
cout << cnt << endl;
}
return 0;
}解后反思
本题暴力+小优化就能过
留着填唯一分解定理的坑
