信息学奥赛实战精讲：OpenJudge NOI 1.5 39题「与7无关的数」深度解析

在信息学奥赛的入门阶段，掌握基础算法和编程思维往往比单纯记忆代码更重要。今天我们要拆解的OpenJudge NOI 1.5第39题「与7无关的数」，正是训练数位处理和逻辑判断的经典案例。这道题表面简单，却蕴含了循环结构、标志位使用、函数封装等多个核心编程概念，特别适合正在准备NOIP/CSP-J/S的选手作为基础训练。

1. 题目本质与数学建模

题目要求计算1到n范围内所有「与7无关的数」的平方和。那么什么样的数才算是「与7无关」？根据题意需要满足两个条件：

1. 非7的倍数 ：即该数不能被7整除（i%7 != 0）
2. 不含数字7 ：该数的每一位数字都不为7

这实际上考察的是 数位分离 和 条件组合 两个基础能力。我们先看一个具体例子：

当n=20时，需要排除：

• 7的倍数：7, 14
• 含数字7的数：7, 17

最终有效的数是：1,2,3,4,5,6,8,9,10,11,12,13,15,16,18,19,20

它们的平方和为：1+4+9+16+25+36+64+81+100+121+144+169+225+256+324+361+400 = 2348

2. 核心算法设计

2.1 数位分离技术

数位分离是处理数字类问题的基本功，其核心是通过循环不断取个位和降位：

while(num > 0) {
    int digit = num % 10;  // 获取当前个位
    num /= 10;             // 去掉已处理的个位
    // 处理digit...
}

这个技巧的数学原理其实是数的位权展开。例如处理1234：

• 第一轮：digit=4，num=123
• 第二轮：digit=3，num=12
• 第三轮：digit=2，num=1
• 第四轮：digit=1，num=0（终止）

2.2 两种实现策略对比

方法一：标志位法

int sum = 0;
for(int i=1; i<=n; ++i) {
    bool has7 = false;
    for(int tmp=i; tmp>0; tmp/=10)
        if(tmp%10 == 7) {
            has7 = true;
            break;
        }
    if(i%7!=0 && !has7)
        sum += i*i;
}

优点 ：

• 逻辑直观，适合初学者理解
• 所有操作集中在主循环中，不需要额外函数

缺点 ：

• 代码嵌套层次较深
• 复用性较差，如果其他地方需要判断"含7"需要重复代码

方法二：函数封装法

bool hasDigit7(int n) {
    for(; n>0; n/=10)
        if(n%10 == 7) return true;
    return false;
}

int main() {
    int n, sum=0;
    cin >> n;
    for(int i=1; i<=n; ++i)
        if(i%7!=0 && !hasDigit7(i))
            sum += i*i;
    cout << sum << endl;
}

优势 ：

• 功能模块化，代码更清晰
• hasDigit7函数可复用
• 主循环逻辑简洁，符合"单一职责"原则

性能提示 ：两种方法时间复杂度都是O(nlogn)，因为每个数的数位处理需要O(logn)时间。

3. 常见错误与调试技巧

3.1 边界条件处理

初学者常犯的错误包括：

• 循环条件写成 i<n 而非 i<=n
• 忽略n本身可能是与7相关的数
• 数位分离时处理0的情况不当

测试用例建议 ：

• n=7（边界值）
• n=17（包含数字7）
• n=21（7的倍数）
• n=70（同时是7的倍数且含数字7）

3.2 逻辑运算符陷阱

注意德摩根定律的应用：

if(!(i%7==0 || has7(i)))  // 正确
// 等价于
if(i%7!=0 && !has7(i))    // 更直观的写法

混淆逻辑与/或运算符是常见错误：

if(i%7!=0 || !has7(i))    // 错误！会包含更多数

3.3 效率优化空间

虽然题目对n的限制不大（通常n≤100），但我们可以思考：

1. 预计算排除 ：先标记所有7的倍数和含7的数
2. 数学方法 ：计算总和减去排除项的平方和
3. 数位DP ：当n很大时（如n≤10^18）的高效算法

4. 举一反三：同类题型拓展

掌握本题后，可以尝试以下变种题目：

1. 与特定数字无关的数 ：如"与3无关的数"
2. 多条件组合 ：如同时不与3和7有关的数
3. 不同的计算方式 ：不求平方和而是求立方和或算术和
4. 反向问题 ：统计与7有关的数的个数

例如，求"与3或5无关的数"的和：

bool isRelated(int n, int d) {
    if(n%d == 0) return true;
    for(; n>0; n/=10)
        if(n%10 == d) return true;
    return false;
}

int sum = 0;
for(int i=1; i<=n; ++i)
    if(!isRelated(i,3) && !isRelated(i,5))
        sum += i;

这类题目在OpenJudge、洛谷等平台的入门板块中很常见，建议完成5-10道类似题目来巩固数位处理能力。