数学

wnm喜欢的数学题

解题思路比较明确，也没啥难的，除了一个比较弱的考点，两数最小公倍数等于两数乘积除以最大公约数。
一个数等于两个数乘积一定能被小于等于的数整除，比如9被1整除（1，9）9被3整除（3，3）平方根3只能算一个因子，所以因子个数就更少了，所以我们直接把全部的因子保存起来，再通过二重循环遍历每一对组合，判断是否满足题目条件。如果满足，答案数加1。
可想而知当初我是多么的弱……这种题目都没时间看……很多时候题目不写一定不对，有了思路就是时间复杂度可能过大，也要去尝试，再去想想优化或者改进思路。

cpp代码搓我还用了GNU的内置函数__gcd以及STL容器vector以及auto关键字

#include <stdio.h>

typedef long long ll;
const int N = 1e3 + 7;
ll num[N]; //保存全部的因子
int cnt; //记录因子个数

ll gcd(ll a, ll b) { //辗转相除法求最大公约数
    while (b) {
        ll tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

int main() {
    ll n;
    scanf("%lld", &n);
    //把全部的因子放在num数组中
    for (ll i = 1; i * i <= n; ++i) {
        if (n % i == 0)
            if (i == n / i)    num[cnt++] = i; //完全平方数只算一次
            else {
                num[cnt++] = i;
                num[cnt++] = n / i;
            }
    }
    int ans = 0;
    for (int i = 0; i < cnt; ++i)
        for (int j = 0; j < cnt; ++j)
            //  最大公约数=两数乘积除以最大公约数
            if (num[i] / gcd(num[i], num[j]) * num[j] == n)
                ++ans;
    printf("%d\n", ans);
    return 0;
}