【例78.1】忽明忽暗

解题思路

编号k被其每个正因子翻转一次，最终亮当且仅当因子数为奇数，即完全平方数。令t=floor√n，所求为1²+…+t²=t(t+1)(2t+1)/6，模质数P时乘6的逆元166666668。

正确性说明

因子d与k/d成对，只有平方根因子无法与不同因子成对，故仅平方数亮。平方和公式准确求出所有亮灯编号和，逆元除6与模意义下的公式等价。

易错点

n到10^18，平方根用整数二分，不依赖浮点边界；乘法先模。

复杂度

时间O(log n)，空间O(1)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    cin >> n;
    long long l = 0, r = 1000000000LL;
    while (l < r) {
        long long mid = (l + r + 1) / 2;
        if (mid <= n / mid)
            l = mid;
        else
            r = mid - 1;
    }
    const long long P = 1000000007;
    long long t = l % P;
    cout << t * ((l + 1) % P) % P * ((2 * l + 1) % P) % P * 166666668 % P << "\n";
    return 0;
}