题意

题目有误，数据上是小于等于而不是小于

给定n，求小于等于n的所有数中，是7的倍数，或10进制写法中含有字符'7'的数字的个数

限制,n 不大于30000

方法

枚举

对于每一个输入，我们枚举从1到这个数，看这些数有多少个是和7相关

和7相关

1. 是7的倍数，直接采用取模运算
2. 包含字符7，每次 除以10检查末位

以题目中的73为例

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<(b);i++)

bool relation(int v){ // 计算v是否和7有关系
    if(v%7 == 0)return true; // 7的倍数
    while(v){ // 某一位是7
        if(v%10==7)return true;
        v/=10;
    }
    return false;
}

int main(){
    int n;
    while(~scanf("%d",&n)){
        int cnt = 0;
        rep(i,1,n+1){ // 从1到当前值
            cnt += relation(i);
        }
        printf("%d\n",cnt);
    }
    return 0;
}

复杂度分析

设查询次数为$mm$

时间复杂度: 我们每次输入会遍历从1到当前值，所以时间复杂度为$O(nm)O(nm)$

空间复杂度: 我们只用了常数大小的空间来记录，所以空间复杂度为$O(1)O(1)$

预处理优化

注意到相邻的两个数，比它们小的和7相关的个数最多差1，

也就是小于等于i-1的和7相关的个数和小于等于i的和7相关的个数相差最多为1

而这个变化值，由i是否和7相关决定

所以有关系式ans[i] = ans[i-1]+relation(i)

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i<(b);i++)
int ans[30010];

bool relation(int v){
    if(v%7 == 0)return true;
    while(v){
        if(v%10==7)return true;
        v/=10;
    }
    return false;
}


int main(){
    rep(i,1,30000+1){
        ans[i] = ans[i-1]+relation(i); // 预处理
    }
    int n;
    while(~scanf("%d",&n)){
        printf("%d\n",ans[n]); // 直接获得答案
    }
    return 0;
}

复杂度分析

时间复杂度: 我们预处理了数据，每次查询直接返回，所以总时间复杂度为$O(n+m)O(n+m)$

空间复杂度: 我们预处理数组为主要的空间占用，所有空间复杂度为$O(n)O(n)$