Description
小明比较喜欢研究各种各样的数字，有一天他发现了一类数，并将这些数命名为“小明数”，下面是“小明数”的定义：
数字的二进制由连续的k个1和连续的k-1个0组成。
比如：
1（二进制为：1，k=1）
6（二进制为：110，k=2）
120（二进制为：1111000，k=4）
496（二进制为：111110000，k=5）
现在给你一个数字n，求他所有的因子里最大的“小明数”。
Input
第1行：一个数T，表示后面用作输入测试的数的数量。（1 <= T <= 10^5)
第2 - T + 1行：每行1个数n。（1 <= n <= 10^5)
Output
共T行每行对应每个测试用例的结果
思路：刚开始没算好时间复杂度所以直接暴力在main函数里面
#include<iostream>
#include<cstring>
using namespace std;
int a[100];
int b[100];
int huansuan(int n,int a[]) {
int p=0;//一共p位数
while(n) {
a[p]=n&1;
n>>=1;
p++;
}
// for(int i = p-1; i>=0; i--) {
// cout<<a[i];
// }
// cout<<endl;
return p;
}
bool ok(int x) {
if(x==1) return true;
int p = huansuan(x,b);
int cnt0=0;
for(int i = 0; i<p; i++) {
if(b[i]==0) cnt0++;
else break;
}
if(cnt0*2+1!=p) return false;//因为这里要考虑到cnt0==0的情况，也就是想到了x==1的情况了
for(int i = cnt0; i<p; i++) {
if(b[i]!=1) return false;
}
return true;
}
int main()
{
int n,t;
cin>>t;
while(t--) {
memset(a,0,sizeof(a));
cin>>n;
huansuan(n,a);
for(int i = n-1; i>=0; i--) {
if(ok(i)) {
printf("%d\n",i);
break;
}
}
}
return 0 ;
}而且没加上是因子的判断，，，很失败、、
TLE之后发现打表，刚开始的打表也是失败的：
//超时做法
#include<iostream>
#include<cstring>
using namespace std;
int a[100];
int b[100];
int db[100005];
int huansuan(int n,int a[]) {
int p=0;//一共p位数
while(n) {
a[p]=n&1;
n>>=1;
p++;
}
// for(int i = p-1; i>=0; i--) {
// cout<<a[i];
// }
// cout<<endl;
return p;
}
bool ok(int x) {
if(x==1) return true;
int p = huansuan(x,b);
int cnt0=0;
for(int i = 0; i<p; i++) {
if(b[i]==0) cnt0++;
else break;
}
if(cnt0*2+1!=p) return false;//因为这里要考虑到cnt0==0的情况，也就是自然想到x==1的情况了
for(int i = cnt0; i<p; i++) {
if(b[i]!=1) return false;
}
return true;
}
void dabiao() {
db[1]=db[2]=1;
for(int i = 2; i<=10005; i++) {
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
huansuan(i,a);
for(int j = i-1; j>=db[i]; j--) {//这样并不能简化运算，复杂度甚至更高了，不像筛法求素数一样，因为这个不是记忆化，
if(ok(j)) { //也就是，你虽然k那层for循环更新了db值，但并不一定是最终结果，所以意义不大
db[i]=j; //建议在看一看线性时间筛法求素数中是怎么降低时间复杂度的！那才是真正的记忆化！
for(int k = i+db[i]; k<=10005; k+=db[i]) {//你这个记忆化卵用没有，只是先找到了较优解，并非最优解所以此处无意义。
db[k]=db[i]; // 只有A*算法类似的才需要较优解，其余情况需要记忆的是最优解才有意义。
}
break;
}
}
}
}
int main()
{
int n,t;
scanf("%d",&t);
dabiao();
while(t--) {
scanf("%d",&n);
printf("%d\n",db[n]);
}
return 0 ;
} 依旧TLE，并且比时间复杂度略高于直接双层for，（ps:其实直接双层for时间复杂度也是o(n^2)，虽然内层不是1~100005，但是取平均，，去掉系数，依旧是o(n^2) ）
下面是思考后的打表：
#include<iostream>
#include<cstring>
using namespace std;
int db[10];
int cnt=0;
void dabiao() {
db[0]=1;cnt++;
db[1]=6;cnt++;//cnt=2;
int n=6;
int tmp1,tmp2;
while(n<=100005) {
tmp1=n<<2;
n=db[cnt]=tmp1+( 1<<cnt );//需要加括号！！！
// cout<<db[cnt]<<endl;
cnt++;
}
}
int main()
{
int n,t;
scanf("%d",&t);
dabiao();
// for(int i = 0; i<cnt; i++) {
// printf("%d\n",db[i]);
// }
while(t--) {
scanf("%d",&n);
if(n==1) {
printf("1\n");
continue;
}
for(int i = cnt-2; i>=0; i--) {//小细节！需要-1！不然就爆零了！
if( n>=db[i] && (n%db[i]==0)) {
printf("%d\n",db[i]);
break;
}
}
}
return 0 ;
}
/*
1
6
28
120
496
2016
8128
32640
130816
*/24ms运行时间、、、还有一点要注意的是，因子的定义！！eg : 6是6的因子！所以
n>=db[i]等号不能拉下！！很气、、
总结：先看题啊算一算时间复杂度，这题数据量1e5，所以不打表就至少1e10，肯定TLE，所以打表是肯定的了，再审题，发现不需要像第一版那样去遍历1e5来找符合小明数的；而应该，根据题目小明数的特点，直接位运算，得到若干个小明数，即：你可以直接找出这些小明数（并且一共就不多，就8个），那为什么还要遍历求呢？直接算把次就好了啊，或者直接提前算好然后再数组里直接赋值初始化，极好极好。
另附网络版：用快速幂做的，但是个人感觉没有必要：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int a[100000];
int cnt = 0;
int q_pow(int a,int b){
int ans = 1;
while(b){
if(b&1)
ans *= a;
b >>= 1;
a *= a;
}
return ans;
}
void getnum(){
int t = 1;
int num;
do{
int tmp = 2 * t - 2;
int tmp2 = t;
num = 0;
while(tmp2){
num += q_pow(2,tmp);
tmp2--;
tmp--;
}
if(num < 100000) a[cnt++] = num;
t++;
}while(num < 100000);
}
int main(){
getnum();
for(int i = 0; i<cnt; i++) {
cout<<a[i]<<endl;
}
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i = cnt-1; i >= 0; i--){
if(n % a[i] == 0){
printf("%d\n",a[i]);
break;
}
}
}
return 0;
}
/*
1
6
28
120
496
2016
8128
32640
*/ 
京公网安备 11010502036488号