考察二进制知识

/* 

 

类型：数论  

 

 

 

给你一个N，让你找到最小的M使得(2 ^ N - 1) % (2 ^ M - 1) = 0。 

2 ^ N的二进制数一定是1后面跟随一些0，那么2 ^ N - 1的二进制数每一位上都是1了， 

所以要想使(2 ^ N - 1) % (2 ^ M - 1) = 0， 

那么其实只要使2 ^ N - 1的二进制数里1的个数能整除2 ^ M - 1的二进制里1的个数就能保证(2 ^ N - 1) % (2 ^ M - 1) = 0。(想一想为什么) 

当输入N时，那么(2 ^ N - 1)的二进制数的1的个数就是N。 

那么此题就是一道水题了，问题变成了求N的最小质因数M。 

 

解析：这道题目很奇葩，算是主要考察 二进制的算法吧。。 

比如说：10101010 有因子1,10,1010，，也就是说可以分成整数个相同的子片段，或者将二进制末尾去0，如1010101片段 

该子片段就能整除原段。。  

 

*/  

#include<iostream>  

#include<cstdio>  

#include<cmath>  

using namespace std;  

  

int main(){  

    int n;  

    while(scanf("%d",&n)!=EOF){  

        int flag=0;  

        if(n%2==0) {  ///剪枝   

            printf("2\n");   

            continue;   

        }  www.zzzyk.com

        int x=(int)sqrt(1.0*n);  

        for(int i=3;i<=x;i+=2)  

            if(n%i==0){   

                printf("%d\n",i);   

                flag=1; break;   

            }  

        if(!flag)   

            printf("%d\n",n);  

    }  

}       

 

补充：软件开发 , C++ ,