题意：一个数的二进制表示如果是一个周期数那么它就是需要的，问[l,r]中有多少个好的数
题解：明显很像数位DP，枚举第一周期的长度，根据第一周期的数值大小来确定有多少种方案，注意首位不能为0.然后就是要注意去重问题，因为对于第一周期长度为k算到的数字，长度为k可以整除的数时必定也算过一遍，减一下就好了，根据这个去重
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<string> 5 #include<algorithm> 6 #include <cmath> 7 using namespace std; 8 typedef long long ll; 9 const ll INF = -100000000000ll; 10 const double eps = 1e-8; 11 const int maxn = 70; 12 const double PI = acos(-1); 13 ll dp[maxn],bin[maxn]; 14 ll l,r; 15 int num[maxn],cnt; 16 void init(){ 17 bin[0] = 1; 18 for(int i = 1;i <= 62;i++) bin[i] = 2*bin[i-1]; 19 } 20 ll cal(int len,int k,ll x) 21 { 22 ll a=0,b=0; 23 for(int i=0;i<k;i++) 24 a+=(num[len-i]<<(k-1-i)); 25 b=a; 26 for(int i=1;i<len/k;i++) 27 b<<=k,b+=a; 28 return a-(1<<(k-1))+1-(b>x); 29 } 30 ll solve(ll u){ 31 cnt = 0; 32 ll ans = u,sum = 0; 33 while(ans > 0){ 34 num[++cnt] = ans % 2; 35 ans /= 2; 36 } 37 memset(dp,0,sizeof(dp)); 38 for(int i = 1;i < cnt;i++){ 39 // memset(dp,0,sizeof(dp)); 40 if(cnt % i != 0) continue; 41 dp[i]= cal(cnt,i,u); 42 for(int j = 1;j < i;j++) 43 if(i % j == 0) dp[i] -= dp[j]; 44 sum += dp[i]; 45 } 46 // cout<<sum<<endl; 47 for(int i = 2;i < cnt;i++){ 48 memset(dp,0,sizeof(dp)); 49 for(int j = 1;j < i;j++){ 50 if(i % j) continue; 51 dp[j] = bin[j-1]; 52 for(int k = 1;k < j;k++) 53 if(j % k == 0) dp[j] -= dp[k]; 54 //cout<<i<<" "<<j<<" "<<dp[j]<<endl; 55 sum += dp[j]; 56 } 57 } 58 // cout<<sum<<endl; 59 return sum; 60 } 61 int main() 62 { 63 // freopen("in.txt","r",stdin); 64 init(); 65 cin>>l>>r; 66 cout<<solve(r) - solve(l-1)<<endl; 67 return 0; 68 }