牛客题目-数圈圈

本题感悟： 遇见这种多组数据的，可以把一些固定的元素存进数组里，这样就可以避免重复计算. 埃氏筛法和欧拉筛法在这一点上就有体现

传送门

#include<iostream>
#include<algorithm>
#include<cstring>
const int maxn=1e6+5;
typedef long long ll;
ll s[10]={1,0,0,0,1,0,1,0,2,1};//个位0-9
ll sum[maxn];//每一个数
using namespace std;
int main()
{
    memset(sum,0,sizeof(sum));
    ll t,a,b,cnt,i;
    for(i=0;i<=maxn;i++)//计算出<=1e6的每个数具有的圈的个数，并存进数组里
    {
        t=i;
        while(t){
            ll tt=t%10;
            sum[i]+=s[tt];
            t/=10;
        }
    }  
    cin>>t;
    while(t--)
    {
        cnt=0;//每组数据都需把计数的变量重置
        cin>>a>>b;
        for(i=a;i<=b;i++) cnt+=sum[i];
        cout<<cnt<<endl;
    }
}