【11.2noip冲刺赛】循环整数（分段打表）

【问题描述】
moreD在学习完循环小数之后发现循环是个很美好的性质。自己只需要记住短短的循环节以及循环次数(次数大于1，且是整数)就可以记住整个数字了。
因为背诵数字变得方便了，moreD决定背诵[L,R]内的所有循环的整数。moreD的背诵计划有T天，但是他不知道每天具体要背多少个数，请你帮助moreD计算出每天需要背诵的数字个数。
如果moreD在某天遇到一个曾经背过的数字，他会义无反顾地重新背诵。
【输入格式】第一行给出一个整数T，表示moreD计划背诵T天的数字。接下来n行,第i行给出2个整数Li,Ri,表示moreD第i天的背诵计划。
【输出格式】输出T行，每行一个整数，表示第i天moreD需要背诵的数字个数。
【输入输出样例】
circulate.in
3
1 10000
55555 66666
10 100

circulate.out
108
2
9
【数据范围】
对于30%的数据 T*MAX{Ri}<=2*10^6
对于70%的数据MAX{Ri}<=2*10^6
对于100%的数据 T<=50000,1<=Li<=Ri<=2*10^18
【样例解释】
对于第2天，moreD只需要背诵55555，66666.
对于第3天，moreD只需要背诵11，22，33，44，55，66，77，88，99

(╯‵□′)╯︵┻━┻10的18次方！！

先让我们最容易想到的思路是：算出1-r的循环数个数，再算出1-l的循环数个数，两者相减就完了；

如何求出1到一个数中循环数的数量，可以用到分治的思想：求一到n的循环数的个数，得到n的长度 length，把它转换成求1-10的length次方中的数量（此处有规律，打表）+10的length次方-n的数量；

比如求1-xxxx（某四位数）中的循环数个数，先求1-1000中的个数（即18），再求1000-xxxx的个数。xxxx可以划分为xx|xx（两个数字为一循环节）且都可以取到10-xx之间的数。因此1000-xxxx中间的循环数的个数=xx-10；所以总的循环数的个数为18+xx-10；

在尝试这个思路时，有一个细节要处理，就是第一个循环节在之后可能取不到（如1-123111，我们取不到123123这个循环数），这时需要将第一个循环节的大小加1；

/*代码如下(╯‵□′)╯︵┻━┻【因为还没测过，正确性有待商榷】

╮(╯▽╰)╭反正我自己的数据都是对的……

ヾ(｡｀Д´｡)楼上滚蛋！赶紧去测啊喂！

= =划掉划掉，这个代码WA了，后面会改正再更新的*/

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

int t;

long long f[];

long long xunhuanjie[];

int l_num[maxn],r_num[maxn];

long long ans[maxn];

int right,left;

void init()

{

    freopen("circulate.in","r",stdin);

    freopen("circulate.out","w",stdout);

}

long long work(int a[],int l)

{

    int d[];

    long long ans=;

    for(int i=;i<l;i++) ans+=f[i];//1到l这个区间最少的循环数个数，作为基数记录下来；

    long long num=;

    for(int i=;i<l;i++)

    {

        if(l%i==)//如果i长度的循环节满足；

        {

            long long p=;

            long long q=;

            int w=;

            for(int j=;j<=i;j++) q=q*+a[j];//记录第一个循环节的大小；

            for(int j=i+;j<=l;j++)

            {

                p=p*+a[j];//记录第一个循环节以后的循环节大小；

                if(j==l||j%i==)

                {

                    if(p>q) break;//如果后面有任意一个循环节比第一个循环节小，则不能取到循环节，如123111，我们取不到循环节123（循环数为123123），此时让循环节加一，如果能取到，退出；

                     else if(p<q) w=;

                    p=;

                }

            }

            xunhuanjie[i]=q-num-w+;//循环节减去循环的基数；

            for(int j=;j<i;j++)

            if(i%j==){

             xunhuanjie[i]-=xunhuanjie[j];//减去重复的循环节；

                 }

            ans+=xunhuanjie[i];

        }

        num=num*;

    }

    return ans;

}

void  biao()//初始化，算出1到10的次方的区间的循环数个数；

{

    for(int i=;i<;i++)

    {

        long long num=;

        for(int j=;j<i;j++)//枚举循环节长度；

        {

            if(i%j==){

                xunhuanjie[j]=num;

                for(int k=;k<j;k++) if(j%k==) xunhuanjie[j]-=xunhuanjie[k];//减去重复的循环节；

                f[i]+=xunhuanjie[j];

            }

            num=num*;

        }

    }

}

void read()

{

    scanf("%d",&t);

    for(int j=;j<=t;j++)

    {

        char l[],r[];

        scanf("%s",l);

        scanf("%s",r);

        left=strlen(l);

        right=strlen(r);

        for(int i=;i<=strlen(l);i++) l_num[i]=l[i-]-'';

        for(int i=;i<=strlen(r);i++) r_num[i]=r[i-]-'';

        ans[j]=work(r_num,right)-work(l_num,left);

    }

}

int main()

{

    //init();

    biao();

    read();

    for(int i=;i<=t;i++) printf("%lld\n",ans[i]);

    return ;

}

巴特西

【11.2noip冲刺赛】循环整数（分段打表）

最新文章

热门文章

巴特西

【11.2noip冲刺赛】 循环整数 （分段打表）

最新文章

热门文章

【11.2noip冲刺赛】循环整数（分段打表）