函数求值（数据过大时会超时）

Question

奇数的最大公因数就是本身，用求和公式直接相加，偶数用循环找出最大因子。
但这样会提交会超时。希望各位帮忙看看

Answer 1

以下内容部分参考ChatGPT模型：

---

对于数据过大时会超时的情况，可以考虑优化算法。对于偶数，可以使用更快的算法，如辗转相除法或欧几里得算法来求最大公因数。对于奇数，可以直接相加而不需要使用循环。同时，可以使用long long类型来避免数据溢出。

以下是优化后的代码示例：

#include <stdio.h>

long long gcd(long long a, long long b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    int n;
    scanf("%d", &n);

    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        if (i % 2 == 0) {
            long long max_factor = 0;
            for (long long j = 1; j * j <= i; j++) {
                if (i % j == 0) {
                    if (j % 2 == 1 && j > max_factor) {
                        max_factor = j;
                    }
                    if ((i / j) % 2 == 1 && (i / j) > max_factor) {
                        max_factor = i / j;
                    }
                }
            }
            sum += max_factor;
        } else {
            sum += i;
        }
    }

    printf("%lld\n", sum);
    return 0;
}

---

如果我的建议对您有帮助、请点击采纳、祝您生活愉快