题目描述
给你一个正整数 n，请你输出对每个 2≤𝑖≤𝑛2≤i≤n，gcd⁡(𝑖∗(𝑖−1)2,𝑖∗(𝑖+1)2)gcd( 2i∗(i−1)​, 2i∗(i+1)) 之和对 109+7取模。
输入描述:
第一行有一个正整数，表示 𝑛。
题目保证对于所有测试用例：2≤𝑛≤109。
输出描述:
输出有一行一个正整数，表示答案模 109+7后的值。

一些定理
gcd(a, b) = gcd(a, b - a);
gcd(a, b) >= |a - b|
x 与 x + 1 与 x - 1互质；

#include <iostream>

using namespace std;

#define ll long long

const int mod = 1e9 + 7;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin >> n;
    ll ans = 0;
    if (n % 2)
    {
        ll d = n / 2;
        ans += (d + 1) * d / 2;
        ans %= mod;
        ans += (3 + n) * (n / 2) / 2;
        ans %= mod;
    }
    else
    {
        ll d = n / 2;
        ans += (d + 1) * d / 2;
        ans %= mod;
        n--;
        ans += (3 + n) * (n / 2) / 2;
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}