与 7 无关的数的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求计算 $1$ ~1~ 到 $n$ ~n~ 之间所有与 $7$ ~7~ 无关的正整数的平方和，其中“与 $7$ ~7~ 无关”指数不能被 $7$ ~7~ 整除，且十进制表示的每一位都不是 $7$ ~7~。核心解法是从 $1$ ~1~ 到 $n$ ~n~ 逐个枚举，对每个数做整除与取模判定，把无关的数平方后累加。

分析

核心观察

一个数是否与 $7$ ~7~ 相关由两件事决定：它对 $7$ ~7~ 取模的结果，以及它的十进制各位数字。题面限制 $n < 100$ ~n < 100~，因此参与判定的每个数至多两位，“某一位上是 $7$ ~7~” 只需检查个位与十位这两个位置。

思路

记 $S$ ~S~ 为满足条件的正整数集合：

$\displaystyle S = \{\, i : 1 \le i \le n,\ i \bmod 7 \ne 0,\ i \bmod 10 \ne 7,\ \lfloor i / 10 \rfloor \bmod 10 \ne 7 \,\}$

记答案为 $A$ ~A~，要求的就是

$\displaystyle A = \sum_{i \in S} i^2$

三个判定条件之间是或的关系：i % 7 == 0 对应“能被 $7$ ~7~ 整除”，i % 10 == 7 对应个位是 $7$ ~7~，i / 10 % 10 == 7 对应十位是 $7$ ~7~。命中任意一条即为相关，跳过；三条都不命中才把 $i^2$ ~i^2~ 累加进答案。

也可以先把 $1 \sim 99$ ~1 \sim 99~ 的相关性一次筛出来做前缀和，但每个数判定的代价已经是 $O(1)$ ~O(1)~，枚举一遍总时间 $O(n)$ ~O(n)~，筛法并不会带来量级上的改进，反而多占一份标记数组，因此直接枚举即可。

平方和规模也需要确认：即使 $1 \sim 99$ ~1 \sim 99~ 全部计入， $1^2 + 2^2 + \cdots + 99^2 = 328350$ ~1^2 + 2^2 + \cdots + 99^2 = 328350~，远远小于 $2^{31} - 1$ ~2^{31} - 1~，32 位有符号整型足以容纳。

具体示例

以样例 $n = 21$ ~n = 21~ 为例。被 $7$ ~7~ 整除的数有 $7, 14, 21$ ~7, 14, 21~，数位上含 $7$ ~7~ 的数有 $7, 17$ ~7, 17~，合并后与 $7$ ~7~ 相关的数是 $7, 14, 17, 21$ ~7, 14, 17, 21~ 四个，剩余 $17$ ~17~ 个正整数与 $7$ ~7~ 无关：

$\displaystyle 1,2,3,4,5,6,8,9,10,11,12,13,15,16,18,19,20$

依次累加它们的平方： $1^2 + \cdots + 6^2 = 91$ ~1^2 + \cdots + 6^2 = 91~， $8^2 + 9^2 = 145$ ~8^2 + 9^2 = 145~， $10^2 + \cdots + 13^2 = 534$ ~10^2 + \cdots + 13^2 = 534~， $15^2 + 16^2 = 481$ ~15^2 + 16^2 = 481~， $18^2 + 19^2 + 20^2 = 1085$ ~18^2 + 19^2 + 20^2 = 1085~，合计 $91 + 145 + 534 + 481 + 1085 = 2336$ ~91 + 145 + 534 + 481 + 1085 = 2336~，与样例输出一致。

注意 $17$ ~17~ 虽然不被 $7$ ~7~ 整除，但个位是 $7$ ~7~，同样要被排除；而 $21$ ~21~ 不含数字 $7$ ~7~，却因被 $7$ ~7~ 整除也要排除。两类条件缺一不可。

算法步骤

读入 n，令累加变量 ans 为 $0$ ~0~。
从 $1$ ~1~ 到 $n$ ~n~ 依次枚举 i。
若 i % 7 == 0、i % 10 == 7、i / 10 % 10 == 7 三者中任意一条成立，说明 i 与 $7$ ~7~ 相关，跳过。
否则令 ans 加上 i * i。
输出 ans。

复杂度分析

时间： $O(n)$ ~O(n)~。枚举 $n$ ~n~ 个数，每个数只做常数次整除、取模与比较。
空间： $O(1)$ ~O(1)~。只需要 n、i、ans 三个整型变量，不需要保存任何序列。

实现注意事项

三条判定是“或”的关系，命中任意一条即为相关；只有全部不命中才计入答案，取反时不要把三个条件写成与。
十位必须单独检查，只写 i % 7 == 0 || i % 10 == 7 会漏掉 $70 \sim 79$ ~70 \sim 79~ 这一类十位为 $7$ ~7~ 的数。
题面限制 $n < 100$ ~n < 100~，所以 $i$ ~i~ 至多两位，i / 10 % 10 就是十位；若把范围推广到任意位数，需要改成逐位取模的循环或直接转字符串判断。
平方和上界为 $328350$ ~328350~，int 足够；即便写成 i * i 也不会溢出，因为单个 $i \le 99$ ~i \le 99~ 时 $i^2 \le 9801$ ~i^2 \le 9801~。
$n \ge 1$ ~n \ge 1~，循环从 $1$ ~1~ 开始；不存在答案为空的输入，不需要特判。
输入只有一个整数，用 cin 直接读入即可，无需按行处理。

源代码

#include <iostream>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;

    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        // 与 7 相关：能被 7 整除，或个位是 7，或十位是 7
        if (i % 7 == 0 || i % 10 == 7 || i / 10 % 10 == 7) {
            continue;
        }
        ans += i * i;
    }

    std::cout << ans << '\n';
    return 0;
}

import sys


def main():
    n = int(sys.stdin.buffer.read().split()[0])

    ans = 0
    for i in range(1, n + 1):
        if i % 7 == 0 or i % 10 == 7 or i // 10 % 10 == 7:
            continue
        ans += i * i

    sys.stdout.write(str(ans) + "\n")


main()

目前没有评论。