NEFU-1669 高木同学的因子(待更新唯一分解定理)

NEFU-1669 高木同学的因子(待更新唯一分解定理)

/ 0评 / 1452次 / 0

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;
}

解后反思

本题暴力+小优化就能过

留着填唯一分解定理的坑

发表回复

您的电子邮箱地址不会被公开。

你好 No.65348