codeforces 215E 求有周期循环的二进制数的个数

101010属于周期循环的二进制，循环次数为3

现在给你十进制的区间，求出有周期循环的数的个数

思路：

枚举循环的周期的长度，但注意周期长度所包含的因子长度不能重复计算。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cstdlib>
 5 typedef long long LL;
 6 int const N = 70;
 7 LL dp[N],p2[N];
 8 int bit[N],ln;
 9 void pre()
10 {
11      p2[0]=1;
12      for(int i=1;i<=64;i++)p2[i]=(p2[i-1]<<1);
13 }
14 LL getsum1(LL n)
15 {
16    LL ans=0;
17    for(int i=1;i<=n/2;i++)
18    {
19        if(n%i==0)
20        {
21           dp[i]=p2[i-1];
22           for(int j=1;j<=i/2;j++)if(i%j==0)dp[i]-=dp[j];
23           ans+=dp[i];
24        }
25    }
26    return ans;
27 }
28 LL getsum2(LL n)
29 {
30    LL num=n;
31    for(ln=0;num;bit[++ln]=num%2,num/=2);
32    LL ans=0;
33    for(int i=1;i<ln;i++)ans+=getsum1(i);
34    for(int i=1;i<=ln/2;i++)
35    {
36        if(ln%i==0)
37        {
38           dp[i]=0LL;
39           LL pre=bit[ln];
40           for(int j=1;j<i;j++)
41           {
42               if(bit[ln-j])dp[i]+=p2[i-j-1];
43               pre=pre*2+bit[ln-j];
44           }
45           LL d=pre;
46           for(int j=1;j<ln/i;j++)pre=pre*p2[i]+d;
47           dp[i]+=(pre<=n);
48           for(int j=1;j<=i/2;j++)if(i%j==0)dp[i]-=dp[j];
49           ans+=dp[i];
50        }
51    }
52    return ans;
53 }
54 int main()
55 {
56     LL l,r;
57     pre();
58     while(~scanf("%I64d %I64d",&l,&r))
59     {
60           l--;
61           printf("%I64d\n",getsum2(r)-getsum2(l));
62     }
63     return 0;
64 }

View Code