考察二进制知识
/*类型：数论 题目链接http://ac.nbutoj.com/Problem/view.xhtml?id=1360给你一个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; } 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); }}