题意

求 0~n 之间的所有满足 自己是自己平方结尾的数的个数

限制: n 不大于10000

方法

预处理+前缀和+查询

注意到 n 的最大值足够小

我们可以提前计算出每个数是不是满足被统计规则的要求。

那么剩下的就是如何判断一个数是否是 它自己平方的结尾。

我们通过比较最后一位，如果相等再删除最后一位的循环方法来实现。

以样例数据$9376^2=879093769376^2\; =\; 87909376$为例

当消耗了值的所有位以后，那么就可以输出是结尾了

代码

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

bool endwith(long long v,long long v2){
    while(v){
        if(v2%10 != v%10)return false; // 末尾判断
        // 移除末尾
        v/=10;
        v2/=10;
    }
    return true;
}

int ans[10010];

int main(){
    for(int i = 0;i<=10000;i++){ // 计算每个数
        ans[i] = endwith(i, i*i);
    } 
    for(int i = 1;i<=10000;i++){ // 前缀和
        ans[i] += ans[i-1];
    } 
    int n;
    while(~scanf("%d",&n)){
        printf("%d\n",ans[n]); // 直接输出答案
    }
    
    return 0;
}

复杂度分析

设查询次数为$mm$

时间复杂度: 主要是两部分，初始化所有值的结果$O(n)O(n)$，对于每次查询直接输出结果，所以每次处理代价为常数,所以总时间复杂度为$O(n+m)O(n+m)$。

空间复杂度: 我们来储存预处理的所有结果$O(n)O(n)$

基于数学的优化

注意到 上述的数学表达式为

$(v^2-v)\mathrm{m}\mathrm{o}\mathrm{d}10^{1+floor(lo{g}_{10}v)}=0(v^2\; -\; v)\; \backslash bmod\; 10^\{1+floor(log\_\{10\}\{v\})\}\; =\; 0$

也就是 $v^2-vv^2-v$ 末尾0的个数大于等于v的位数，也就是$v(v-1)v(v-1)$ 中包含的5和2的因子个数,大于等于v的位数

因为5的幂次比2的同样幂次更大，其范围内倍数更少，我们只需要在 5的幂次的倍数，和它加1后的值中寻找。

所以 需要找的数有

$0,10,1$ 直接就满足

对于 $ii$ 次方 $10^{i-1}10^\{i-1\}$ 到 $10^{i}10^i$之间，又是$5^{i}5^i$的倍数,很少的范围需要搜索了

所以满足条件的个数也足够少, 按题目的限制只有9个满足，十分的少

代码

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

int main(){
    vector<int> ans = {0,1};
    for(int pwr = 1;pwr < 5;pwr++){ // 次方
        int base = 1; // 5 的 幂次
        int mod = 1; // 10 的 幂次
        for(int i = 0;i<pwr;i++){
            base *= 5;
            mod *= 10;
        }
        for(int v = base;v < mod;v+=base){
            if(v <= mod/10)continue; // 注意范围控制
            if( (v * (v-1)) % mod == 0 ){ // v满足数学表达式
                ans.push_back(v);
            }
            if( (v * (v+1)) % mod == 0 ){ // v+1满足数学表达式
                ans.push_back(v+1);
            }
        }
    }
    int n;
    while(~scanf("%d",&n)){
        int cnt = 0; // 小于等于查询值满足题意的个数
        for(auto v:ans){ // 遍历结果
            if(v > n)break;
            cnt++;
        }
        printf("%d\n",cnt);
    }
    
    return 0;
}

复杂度分析

范围内上述查找个数为$kk$个,有$cntcnt$个满足条件

时间复杂度: 只有满足数学查找的需要被搜索, 每次询问我们查询一遍数组,总时间复杂度为$O(k+m\cdot k)O(k+m\backslash cdot\; k)$

空间复杂度: 我们只存储了满足要求的值,$O(cnt)O(cnt)$